Pagini recente » Cod sursa (job #2206148) | Cod sursa (job #2200295) | Cod sursa (job #842855) | Cod sursa (job #1923269) | Cod sursa (job #2148024)
#include <bits/stdc++.h>
FILE *fin = freopen("ctc.in", "r", stdin);
FILE *fout = freopen("ctc.out", "w", stdout);
using namespace std;
const int MAX = 1e5 + 2;
int n, m, t, count_scc;
vector <int> G[MAX];
bitset <MAX> seen;
vector <int> scc[MAX];
vector <int> st;
int low[MAX], disc[MAX];
void SCC(int node){
while(!st.empty() && st.back() != node){
int x = st.back();
seen.reset(x);
scc[count_scc].push_back(x);
st.pop_back();
}
scc[count_scc].push_back(node);
st.pop_back();
seen.reset(node);
}
void dfs(int node){
st.push_back(node);
low[node] = disc[node] = ++ t;
seen.set(node);
for(int son : G[node]){
if(!disc[son]){
dfs(son);
low[node] = min(low[node], low[son]);
} /// tree edge
else if(seen.test(son))
low[node] = min(low[node], disc[son]); /// back edge
/// else we encounter a cross edge which should be avoid
}
if(low[node] == disc[node]){
SCC(node);
count_scc ++;
}
}
void Write(){
printf("%d\n", count_scc);
for(int i = 0; i < count_scc; ++ i){
for(int node : scc[i])
printf("%d ", node);
printf("\n");
}
}
int main(){
int u, v;
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; ++ i){
scanf("%d%d", &u, &v);
G[u].push_back(v);
}
for(int i = 1; i <= n; ++ i)
if(!disc[i])
dfs(i);
Write();
return 0;
}