Pagini recente » Cod sursa (job #2747975) | Cod sursa (job #2908668) | Cod sursa (job #2373895) | Cod sursa (job #2329358) | Cod sursa (job #2351365)
#include <bits/stdc++.h>
std::vector< int > nd[100001];
std::vector< int > inv[100001];
int ord[100000];
int viz[100001];
std::vector< int > af[100000];
int q=0,c=0;
void dfs(int k){
viz[k]=1;
for(int i=0;i<nd[k].size();i++){
if(viz[nd[k][i]]==0){
dfs(nd[k][i]);
}
}
ord[q]=k;
q++;
}
void dfs1(int k){
af[c].push_back(k);
viz[k]=0;
for(int i=0;i<inv[k].size();i++){
if(viz[inv[k][i]]==1){
dfs1(inv[k][i]);
}
}
}
int main()
{
int n,m,a,b,i;
FILE*fi,*fo;
fi=fopen("ctc.in","r");
fo=fopen("ctc.out","w");
fscanf(fi,"%d%d",&n,&m);
for(i=0;i<m;i++){
fscanf(fi,"%d%d",&a,&b);
nd[a].push_back(b);
inv[b].push_back(a);
}
for(i=1;i<=n;i++){
if(viz[i]==0)
dfs(i);
}
for(i=n-1;i>=0;i--){
if(viz[ord[i]]==1)
{
dfs1(ord[i]);
c++;
}
}
fprintf(fo,"%d\n",c);
for(i=0;i<c;i++){
for(int j=0;j<af[i].size();j++)
fprintf(fo,"%d ",af[i][j]);
fprintf(fo,"\n");
}
fclose(fi);
fclose(fo);
return 0;
}