Cod sursa(job #549200)

Utilizator chrisuPirvu Cristina chrisu Data 8 martie 2011 11:14:26
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include<stdio.h>
#include<vector>
#define N 200001

using namespace std;

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

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

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);
	}
}


int main()
{
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);

	citire();
	int i;
	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(size_t j=0 ; j<c[i].size() ; j++)
			printf("%d ",c[i][j]);
		printf("\n");
	}
	
	return 0;
}