Cod sursa(job #549173)

Utilizator alexandra_naeNae Alexandra Beatrice alexandra_nae Data 8 martie 2011 10:48:41
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include<stdio.h>
#include<vector>
#define N 200001
using namespace std;

vector<int> s[N];
vector<int> p[N];
vector<int> c[N];

int m,n,nr;
bool v1[N],v2[N];
int ordine[N];

void citire()
{
	int x,y,a;
	scanf("%d%d",&n,&m);
	while(m--)
	{
		scanf("%d%d",&x,&y);
		s[x].push_back(y);
		p[y].push_back(x);
	}
}

void dfs1(int x)
{
	int a;
	v1[x] = true;
	for(int i=0;i<s[x].size();++i)
	{
		a = s[x][i];
		if(!v1[a])
			dfs1(a);
	}
	ordine[++nr] = x;
}

void dfs2(int x)
{
	int a;
	v2[x] = true;
	c[nr].push_back(x);
	for(int i=0;i<p[x].size();++i)
	{
		a = p[x][i];
		if(!v2[a])
			dfs2(a);
	}
}

void rezolva()
{
	for(int i=1;i<=n;i++)
		if(!v1[i])
			dfs1(i);
	nr = 0;
	for(int i=n;i>=1;i--)
		if(!v2[ordine[i]])
		{
			++nr;
			dfs2(ordine[i]);
		}
	printf("%d\n",nr);
	for(int i=1;i<=nr;i++)
	{
		for(size_t 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();
	rezolva();
	return 0;
}