Pagini recente » Cod sursa (job #1428755) | Cod sursa (job #1605755) | Cod sursa (job #1357643) | Cod sursa (job #791375) | Cod sursa (job #2324686)
#include <cstdio>
#include <stack>
#include <vector>
#define nmax 100001
using namespace std;
FILE *f,*g;
int n,m;
bool viz1[nmax],viz2[nmax];
stack <int> S;
vector <int> V[nmax];
vector <int> Vt[nmax];
vector <int> V2[nmax];
void Citire()
{int i,x,y;
fscanf(f,"%d%d",&n,&m);
for(i=1;i<=m;i++)
{fscanf(f,"%d%d",&x,&y);
V[x].push_back(y); Vt[y].push_back(x);
}
}
void DFS1(int x)
{int i;
vector <int>::iterator it;
viz1[x]=1;
for(it=V[x].begin();it!=V[x].end();it++)
if(!viz1[*it]) DFS1(*it);
S.push(x);
}
void DFS2(int x, int k)
{int i;
vector <int>::iterator it;
viz2[x]=1;
for(it=Vt[x].begin();it!=Vt[x].end();it++)
if(!viz2[*it]) DFS2(*it,k);
V2[k].push_back(x);
}
int main()
{int c,k=0,i;
vector <int>::iterator it;
f=fopen("ctc.in","r");
g=fopen("ctc.out","w");
Citire();
fclose(f);
for(i=1;i<=n;i++)
if(viz1[i]==0) DFS1(i);
while(!S.empty())
{c=S.top(); S.pop();
if(viz2[c]==0)
{k++; DFS2(c,k);}
}
fprintf(g,"%d",k);
fprintf(g,"\n");
for(i=1;i<=n;i++)
{for(it=V2[i].begin();it!=V2[i].end();++it)
fprintf(g,"%d ",*it);
fprintf(g,"\n");
}
return 0;
}