Cod sursa(job #384009)

Utilizator borsoszalanBorsos Zalan borsoszalan Data 18 ianuarie 2010 21:26:50
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#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;
}