Pagini recente » Monitorul de evaluare | Istoria paginii utilizator/vlad231 | Atasamentele paginii Clasament vendetta_dc4 | Atasamentele paginii test913 | Cod sursa (job #2922182)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
class Graph {
private:
int size_;
vector<vector<int>> edges_;
vector<vector<int>> ctc_;
vector<int> low_;
vector<int> d_;
vector<bool> on_stk_;
stack<int> stk_;
public:
Graph(int size) {
size_ = size;
edges_.resize(size_);
}
void addEdge(int a, int b) {
edges_[a].push_back(b);
}
int dfs(int node, int& index) {
d_[node] = index;
index++;
low_[node] = d_[node];
stk_.push(node);
on_stk_[node] = true;
// string space(d_[node], ' ');
// cerr << space << node + 1 << endl;
for (int i = 0; i < edges_[node].size(); i++) {
int next = edges_[node][i];
if (d_[next] == 0) {
low_[node] = min(low_[node], dfs(next, index));
} else if (on_stk_[next]) {
low_[node] = min(low_[node], d_[next]);
}
}
// cerr << space << node + 1 << " " << d_[node] << " " << low_[node] << endl;
if (low_[node] == d_[node]) {
ctc_.push_back(vector<int>());
while (stk_.top() != node) {
ctc_.back().push_back(stk_.top());
stk_.pop();
}
ctc_.back().push_back(stk_.top()); // node
stk_.pop();
}
return low_[node];
}
void computeCtc() {
low_.clear();
d_.clear();
on_stk_.clear();
ctc_.clear();
low_.resize(size_);
d_.resize(size_, 0);
on_stk_.resize(size_, false);
int index = 1;
for (int i = 0; i < size_; i++) {
if (d_[i] == 0) {
dfs(i, index);
}
}
}
void printCtc(ostream& out) {
out << ctc_.size() << "\n";
for (int i = 0; i < ctc_.size(); i++) {
for (int j = 0; j < ctc_[i].size(); j++) {
out << ctc_[i][j] + 1 << " ";
}
out << "\n";
}
}
};
int main() {
ifstream in("ctc.in");
ofstream out("ctc.out");
int n, m; in >> n >> m;
Graph graph(n);
for(int i = 0; i < m; i++) {
int a, b; in >> a >> b;
a--; b--;
graph.addEdge(a, b);
}
graph.computeCtc();
graph.printCtc(out);
return 0;
}