Pagini recente » Cod sursa (job #2687052) | Cod sursa (job #2293044) | Cod sursa (job #1315514) | Cod sursa (job #1517469) | Cod sursa (job #856852)
Cod sursa(job #856852)
#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,k1;
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[k1].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);
k1=0;
for (int i=1;i<=n;i++)
mark[i]=0;
for ( int i=n;i>=1;i--)
if (mark[nodu[i]]==0)
{
k1++;
dfs2(nodu[i]);
}
fprintf(g,"%d\n",k1);
for (int i=1;i<=k1;i++)
{
for (it=CTC[i].begin();it!=CTC[i].end();it++)
{
int j= (*it);
fprintf(g,"%d ",j);
}
fprintf(g,"\n");
}
return 0;
}