Pagini recente » Cod sursa (job #1364793) | Cod sursa (job #1943335) | Cod sursa (job #2587284) | Cod sursa (job #2219859) | Cod sursa (job #2822251)
#include <bits/stdc++.h>
using namespace std;
#ifdef INFOARENA
ifstream fin("ctc.in");
ofstream fout("ctc.out");
#define cout fout
#define cin fin
#endif // INFOARENA
vector <vector <int>> g, cc;
stack <int> st;
const int NMAX = 1e5;
int ind[NMAX + 5], low[NMAX + 5], k, cnt;
bool onstack[NMAX + 5];
void dfs(int u) {
onstack[u] = true;
st.push(u);
ind[u] = ++cnt;
low[u] = ind[u];
for(int adj : g[u]) {
if(!ind[adj]) {
dfs(adj);
low[u] = min(low[u], low[adj]);
} else if(onstack[adj]) low[u] = min(low[u], ind[adj]);
}
if(low[u] == ind[u]) {
cc.push_back({u}); k++;
while(st.top() != u) {
onstack[st.top()] = false;
cc[k - 1].push_back(st.top());
st.pop();
}
st.pop();
onstack[u] = false;
}
}
int main()
{
int n, m, u, v;
cin >> n >> m;
g.resize(n + 1);
for(int i = 1; i <= m; i++)
cin >> u >> v,
g[u].push_back(v);
for(int i = 1; i <= n; i++) if(!ind[i])
dfs(i);
cout << k << "\n";
for(int i = 0; i < k; i++, cout << "\n") for(int x : cc[i])
cout << x << " ";
return 0;
}