Pagini recente » Cod sursa (job #2747763) | Cod sursa (job #462397) | Cod sursa (job #2038065) | Cod sursa (job #42818) | Cod sursa (job #2909322)
#include <bits/stdc++.h>
#define NMAX 100005
using namespace std;
int n, m;
vector <int> adj[NMAX];
bool viz[NMAX],inStack[NMAX];
int timestamp;
int found[NMAX], low_link[NMAX];
stack <int> nodes_stack;
vector <vector <int> > all_scc;
void dfs(int x) {
found[x] = low_link[x] = timestamp++;
nodes_stack.push(x);
inStack[x] = 1;
viz[x] = 1;
for (auto y : adj[x]) {
if (!viz[y]) {
dfs(y);
low_link[x] = min(low_link[x], low_link[y]);
} else {
if (inStack[y]) {
low_link[x] = min(low_link[x], low_link[y]);
}
}
}
vector <int> scc;
int el;
if (low_link[x] == found[x]) {
do {
el = nodes_stack.top();
inStack[el] = 0;
nodes_stack.pop();
scc.push_back(el);
} while (el != x);
all_scc.push_back(scc);
}
}
int main() {
ifstream cin("ctc.in");
ofstream cout("ctc.out");
cin >> n >> m;
for (int i = 1, x, y; i <= m; i++) {
cin >> x >> y;
adj[x].push_back(y);
}
for (int i = 1; i <= n; i++) {
if (!viz[i]) {
dfs(i);
}
}
cout << all_scc.size() << endl;
for (auto scc : all_scc) {
for (auto node : scc) {
cout << node << " ";
}
cout << "\n";
}
}