Pagini recente » Cod sursa (job #1397125) | Cod sursa (job #537007) | Cod sursa (job #3206888) | Cod sursa (job #2701687) | Cod sursa (job #2195497)
#include <iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=100005;
vector<int> vec[N];
vector<int> vec2[N];
vector<int> afis[N];
int viz1[N],viz2[N],sortattop[N];
int t;
int ntc;
int n;
void dfs1(int x){
viz1[x]=true;
int a;
for(int i=0;i<vec[x].size();i++){
a=vec[x][i];
if(viz1[a]==false){
dfs1(a);
}
}
t++;
sortattop[n+1-t]=x;
}
void dfs2(int x){
viz2[x]=true;
afis[ntc].push_back(x);
int a;
for(int i=0;i<vec2[x].size();i++){
a=vec2[x][i];
if(viz2[a]==false){
dfs2(a);
}
}
}
int main()
{
FILE*fin,*fout;
int m;
fin=fopen("ctc.in","r");
fout=fopen("ctc.out","w");
int i,j,x1,x2;
fscanf(fin,"%d%d",&n,&m);
for(i=1;i<=m;i++){
fscanf(fin,"%d%d",&x1,&x2);
vec[x1].push_back(x2);
vec2[x2].push_back(x1);
}
for(i=1;i<=n;i++){
if(viz1[i]==false)
dfs1(i);
}
for(i=1;i<=n;i++){
if(viz2[sortattop[i]]==false){
ntc++;
dfs2(sortattop[i]);
}
}
fprintf(fout,"%d",ntc);
for(i=1;i<=ntc;i++){
for(j=0;j<afis[i].size();j++){
fprintf(fout,"%d ",afis[i][j]);
}
fprintf(fout,"\n");
}
return 0;
}