Pagini recente » Cod sursa (job #2746501) | Cod sursa (job #582814) | Cod sursa (job #3127526) | Cod sursa (job #2662330) | Cod sursa (job #775495)
Cod sursa(job #775495)
#include <stdio.h>
#include <set>
using namespace std;
FILE *fi,*fo;
int n,m;
int i,v1,v2,v;
set <int> G[100001];
set <int> GT[100001];
set <int> CTC[100001];
set <int> :: iterator it;
int nrc;
int S[100001],k;
int VIZ[100001];
void df1(int v)
{
set <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)
{
set <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].insert(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].insert(v2);
GT[v2].insert(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;
k=n;
while (k>0)
{
nrc++;
df2(S[k]);
k-=CTC[nrc].size();
}
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;
}