Pagini recente » Cod sursa (job #550285) | Cod sursa (job #1503861) | Cod sursa (job #2264922) | Cod sursa (job #1217046) | Cod sursa (job #775498)
Cod sursa(job #775498)
#include <stdio.h>
#include <vector>
using namespace std;
FILE *fi,*fo;
int n,m;
int i,v1,v2,v;
vector <int> G[100001];
vector <int> GT[100001];
vector <int> CTC[100001];
vector <int> :: iterator it;
int nrc;
int S[100001],k;
int VIZ[100001];
void df1(int v)
{
vector <int> :: iterator it;
int i;
VIZ[v]=1;
for (it=G[v].begin();it!=G[v].end();it++)
{
i=(*it);
if (VIZ[i]==0)
df1(i);
}
S[++k]=v;
}
void df2(int v)
{
vector <int> :: iterator it;
int i;
VIZ[v]=1;
for (it=GT[v].begin();it!=GT[v].end();it++)
{
i=(*it);
if (VIZ[i]==0)
df2(i);
}
CTC[nrc].push_back(v);
}
int main()
{
fi=fopen("ctc.in","r");
fo=fopen("ctc.out","w");
fscanf(fi,"%d%d",&n,&m);
for (i=1;i<=m;i++)
{
fscanf(fi,"%d%d",&v1,&v2);
G[v1].push_back(v2);
GT[v2].push_back(v1);
}
for (v=1;v<=n;v++)
if (VIZ[v]==0)
df1(v);
nrc=0;
/*for (i=1;i<=n;i++)
fprintf(fo,"%d ",S[i]);*/
for (i=1;i<=n;i++)
VIZ[i]=0;
for (i=n;i>=1;i--)
if (VIZ[S[i]]==0)
{
nrc++;
df2(S[i]);
}
fprintf(fo,"%d\n",nrc);
for (i=1;i<=nrc;i++)
{
for (it=CTC[i].begin();it!=CTC[i].end();it++)
fprintf(fo,"%d ",(*it));
fprintf(fo,"\n");
}
fclose(fi);
fclose(fo);
return 0;
}