Pagini recente » Cod sursa (job #77760) | Cod sursa (job #2587161) | Cod sursa (job #114341) | Cod sursa (job #1729505) | Cod sursa (job #900382)
Cod sursa(job #900382)
#include <iostream>
#include <cstdio>
using namespace std;
int N,M,v1[200001][3],coada[100001][2];
bool ps[100001],ms[100001],viz[100001],viz2[100001];
void citire()
{
int i;
scanf("%d %d", &N, &M);
for(i=1;i<=M;i++)
scanf("%d %d",&v1[i][1], &v1[i][2]);
}
void DFS1(int k)
{
int i;
ps[k]++;
for(i=1;i<=M;i++)
if(v1[i][1]==k && ps[v1[i][2]]==0)
DFS1(v1[i][2]);
}
void DFS2(int k)
{
int i;
ms[k]++;
for(i=1;i<=M;i++)
if(v1[i][2]==k && ms[v1[i][1]]==0)
DFS2(v1[i][1]);
}
void ctc()
{
int i,j,x=0,t=0;
for(i=1;i<=N;i++)
if(viz[i]==0)
{
DFS1(i);
DFS2(i);
for(j=1;j<=N;j++)
if(ps[j]==1 && ms[j]==1)
{
viz[j]=1;
coada[++x][0]=j;
}
coada[x][1]=1;
for(j=1;j<=N;j++)
{
ps[j]=0;
ms[j]=0;
}
t++;
}
printf("%d\n" ,t);
}
void afis()
{
int i=0;
while(i<N)
{
do{
i++;
printf("%i " ,coada[i][0]);
}while(coada[i][1]==0);
printf("\n");
}
}
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
citire();
ctc();
afis();
return 0;
}