Pagini recente » Cod sursa (job #542429) | Cod sursa (job #1554698) | Cod sursa (job #2548990) | Cod sursa (job #1156953) | Cod sursa (job #856848)
Cod sursa(job #856848)
#include <stdio.h>
#include <vector>
using namespace std;
int n,m;
vector <int> G[100001];
vector <int> Gi[100001];
vector <int> CTC[100001];
vector <int> :: iterator it;
int mark[100001], nodu[100001],k;
void dfs1(int vf)
{
vector <int> :: iterator it;
mark[vf]=1;
for (it=G[vf].begin();it!=G[vf].end();it++)
{
int i= (*it);
if (mark[i]==0) dfs1(i);
}
nodu[++k]=vf;
}
void dfs2(int vf)
{
vector <int> :: iterator it;
mark[vf]=1;
for (it=Gi[vf].begin();it!=Gi[vf].end();it++)
{
int i= (*it);
if (mark[i]==0) dfs2(i);
}
CTC[k].push_back(vf);
}
int main()
{
vector <int> :: iterator it;
FILE *f,*g;
f=fopen("ctc.in","r");
g=fopen("ctc.out","w");
fscanf(f,"%d%d",&n,&m);
int x,y;
for (int i=1;i<=m;i++)
{
fscanf(f,"%d%d",&x,&y);
G[x].push_back(y);
Gi[y].push_back(x);
}
for (int i=1;i<=n;i++)
if (mark[i]==0) dfs1(i);
k=0;
for (int i=1;i<=n;i++)
mark[i]=0;
for ( int i=n;i>=1;i--)
if (mark[nodu[i]]==0)
{
k++;
dfs2(nodu[i]);
}
printf("%d\n",k);
for (int i=1;i<=k;i++)
{
for (it=CTC[i].begin();it!=CTC[i].end();it++)
{
int j= (*it);
fprintf(g,"%d ",j);
}
fprintf(g,"\n");
}
return 0;
}