Pagini recente » Cod sursa (job #2338709) | Cod sursa (job #2518872) | Cod sursa (job #3250175) | Cod sursa (job #777359) | Cod sursa (job #3296221)
#include <stdio.h>
#include <vector>
#define MAXN 100000
int q[MAXN], k, last, n;
std::vector <int> edges[MAXN+1];
std::vector <int> redges[MAXN+1];
std::vector <int> sol[MAXN+1];
int t;
int top[MAXN+1], j;
int f[MAXN+1];
void dfs1(int node){
f[node]=1;
for(auto x : edges[node])
if(!f[x])
dfs1(x);
top[j++]=node;
}
void reverse(){
int i;
for(i=1; i<=n; i++)
for(auto x : edges[i])
redges[x].push_back(i);
}
void dfs2(int node){
f[node]=-1;
sol[t].push_back(node);
for(auto x : redges[node])
if(f[x]!=-1)
dfs2(x);
}
void solve(){
int i;
for(i=1; i<=n; i++){
if(!f[i])
dfs1(i);
}
reverse();
for(i=n-1; i>=0; i--){
if(f[top[i]]!=-1){
dfs2(top[i]);
t++;
}
}
FILE *fout=fopen("ctc.out", "w");
fprintf(fout, "%d\n", t);
for(i=0; i<t; i++){
for(auto x : sol[i]){
fprintf(fout, "%d ", x);
}
fprintf(fout, "\n");
}
fclose(fout);
}
int main()
{
FILE *fin;
int m,i,x,y;
fin=fopen("ctc.in", "r");
fscanf(fin, "%d%d", &n, &m);
for(i=0; i<m; i++){
fscanf(fin, "%d%d", &x, &y);
edges[x].push_back(y);
}
solve();
return 0;
}