Cod sursa(job #551013)

Utilizator skullLepadat Mihai-Alexandru skull Data 10 martie 2011 11:24:35
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include<stdio.h>
#include<vector>
#define nmax 200005

using namespace std;

vector<int> succ[nmax];
vector<int> pred[nmax];
vector<int> c[nmax];

int N, nr;
bool viz1[nmax], viz2[nmax];
int ordine[nmax];

void citire()
{
	int x, y, M;
	scanf("%d%d", &N, &M);
	while( M-- )
	{
		scanf("%d%d",&x,&y);
		succ[x].push_back(y);
		pred[y].push_back(x);
	}
}

void dfs1(int x)
{
	int i,y;
	viz1[x] = true;
	for(i = 0; i < succ[x].size(); ++i)
	{
		y = succ[x][i];
		if(!viz1[y])
			dfs1(y);
	}
	ordine[++nr] = x;
}

void dfs2(int x)
{
	int i,y;
	viz2[x] = true;
	c[nr].push_back(x);
	for(i=0;i < pred[x].size();++i)
	{
		y = pred[x][i];
		if(!viz2[y])
			dfs2(y);
	}
}

void solve()
{
	int i, j;
	for(i = 1;i <= N; i++)
		if(!viz1[i])
			dfs1(i);
	nr = 0;
	for(i = N;i>=1;i--)
		if(!viz2[ordine[i]])
		{
			++nr;
			dfs2(ordine[i]);
		}
	printf("%d\n",nr);
	for(i = 1;i <= nr; i++)
	{
		for(j = 0 ; j < c[i].size() ; j++)
			printf("%d ",c[i][j]);
		printf("\n");
	}
}

int main()
{
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	citire();
	solve();
	return 0;
}