Cod sursa(job #252195)

Utilizator AndreyPAndrei Poenaru AndreyP Data 3 februarie 2009 23:32:31
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include<stdio.h>
#include<algorithm>
#include<list>
using namespace std;
#define pb push_back
#define N 100010
#define M 200010
int n,m,cate;
list<int> a[N];
bool viz[N];
int post[M];
list<int> at[N];
bool vizt[N];
int postt[M];
inline void citire()
{
	scanf("%d%d",&n,&m);
	int x,y;
	for(; m; --m)
	{
		scanf("%d%d",&x,&y);
		a[x].pb(y);
		at[y].pb(x);
	}
}
void dfs(int k)
{
	viz[k]=true;
	for(list<int>::iterator it=a[k].begin(); it!=a[k].end(); ++it)
	{
		if(!viz[*it])
			dfs(*it);
	}
	post[++post[0]]=k;
}
void dfst(int k)
{
	vizt[k]=true;
	for(list<int>::iterator it=at[k].begin(); it!=at[k].end(); ++it)
	{
		if(!vizt[*it])
			dfst(*it);
	}
	postt[++postt[0]]=k;
}
inline void rezolva()
{
	for(int i=1; i<=n; ++i)
	{
		if(!viz[i])
			dfs(i);
	}
	for(int i=n; i; --i)
	{
		if(!vizt[post[i]])
		{
			++cate;
			dfst(post[i]);
			++postt[0];
		}
	}
}
inline void scrie()
{
	printf("%d\n",cate);
	for(int i=1; i<=postt[0]; ++i)
	{
		if(postt[i])
			printf("%d ",postt[i]);
		else
			printf("\n");
	}
}
int main()
{
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	citire();
	rezolva();
	scrie();
	return 0;
}