Pagini recente » Cod sursa (job #797987) | Cod sursa (job #1650018) | Cod sursa (job #673521) | Cod sursa (job #2449543) | Cod sursa (job #384009)
Cod sursa(job #384009)
#include<stdio.h>
#include<vector>
#include<list>
using namespace std;
#define nmax 200002
int n,m,i,j,x,y;
list<int> v[nmax],vt[nmax];
bool viz[nmax], vizt[nmax];
int poz[nmax], pozt[nmax];
int nb;
void dfs(int k)
{
viz[k]=true;
int j;
list<int>::iterator it;
for(it=v[k].begin(); it!=v[k].end(); it++)
if(!viz[*it])
dfs(*it);
poz[++poz[0]]=k;
}
void dfst(int k)
{
vizt[k]=true;
int j;
list<int>::iterator it;
for(it=vt[k].begin(); it!=vt[k].end(); it++)
if(!vizt[*it])
dfst(*it);
pozt[++pozt[0]]=k;
}
void read()
{
scanf("%d %d", &n, &m);
for(i=1;i<=m;i++)
{
scanf("%d %d", &x, &y);
v[x].push_back(y);
vt[y].push_back(x);
}
}
void kosaraju()
{
for(i=1;i<=n;i++)
if(viz[i]==false)
dfs(i);
for(i=n;i>=1;i--)
if(vizt[poz[i]]==false)
{
nb++;
dfst(poz[i]);
pozt[0]++;
}
}
void write()
{
printf("%d\n", nb);
for(i=1;i<=pozt[0];i++)
if(pozt[i]==0)
printf("\n");
else printf("%d ", pozt[i]);
}
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
read();
kosaraju();
write();
return 0;
}