Pagini recente » Cod sursa (job #2137399) | Cod sursa (job #1922304) | Cod sursa (job #1571167) | Cod sursa (job #2617777) | Cod sursa (job #1966285)
#include <bits/stdc++.h>
#define maxN 100002
FILE *fin = freopen("ctc.in", "r", stdin);
FILE *fout = freopen("ctc.out", "w", stdout);
using namespace std;
int N, M;
vector <int> G[maxN];
vector <int> Gt[maxN];
vector <int> st;
int no_scc;
vector <int> scc[maxN];
bitset <maxN> used;
void dfs(int node){
used.set(node);
for(int son : G[node])
if(!used.test(son))
dfs(son);
st.push_back(node);
}
void SCC(int node){
used.set(node);
scc[no_scc].push_back(node);
for(int son : Gt[node])
if(!used.test(son))
SCC(son);
}
int main(){
scanf("%d %d", &N, &M);
for(int i = 1; i <= M; ++ i){
int x, y;
scanf("%d %d", &x, &y);
G[x].push_back(y);
Gt[y].push_back(x);
}
for(int i = 1; i <= N; ++ i)
if(!used.test(i))
dfs(i);
used.reset();
for(int i = 0; i < N; ++ i){
int node = st[N - i - 1];
if(!used.test(node)){
SCC(node);
no_scc ++;
}
}
printf("%d\n", no_scc);
for(int i = 0; i < no_scc; ++ i){
for(int node : scc[i])
printf("%d ", node);
printf("\n");
}
return 0;
}