Pagini recente » Cod sursa (job #2371929) | Cod sursa (job #101363) | Cod sursa (job #2704118) | Cod sursa (job #777369) | Cod sursa (job #1638173)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
constexpr int kMaxN = 100000;
int n, m;
std::vector<int> edges[kMaxN+1];
std::vector<std::vector<int> > strongly_connected_components;
bool on_stack[kMaxN+1];
int predecesor[kMaxN+1], index[kMaxN+1], static_index;
std::stack<int> S;
void computeScc(int x)
{
++static_index;
index[x] = static_index;
predecesor[x] = index[x];
on_stack[x] = true;
S.push(x);
for(auto y : edges[x]) {
if(index[y] == 0) {
computeScc(y);
predecesor[x] = std::min(predecesor[x], predecesor[y]);
}
else if(on_stack[y]) {
predecesor[x] = std::min(predecesor[x], index[y]);
}
}
if(predecesor[x] == index[x]) {
std::vector<int> scc;
while(S.top() != x) {
scc.push_back(S.top());
on_stack[S.top()] = false;
S.pop();
}
scc.push_back(x);
on_stack[x] = false;
S.pop();
strongly_connected_components.push_back(std::move(scc));
}
}
void computeTarjan()
{
for(int i = 1; i <= n; ++i) {
if(index[i] == 0) computeScc(i);
}
}
int main()
{
std::ifstream in("ctc.in");
std::ofstream out("ctc.out");
in>>n>>m;
for(int x, y, i = 1; i <= m; ++i) {
in>>x>>y;
edges[x].push_back(y);
}
computeTarjan();
out<<strongly_connected_components.size()<<'\n';
for(auto scc : strongly_connected_components) {
for(auto x : scc) out<<x<<' ';
out<<'\n';
}
return 0;
}