Cod sursa(job #829929)

Utilizator AnteusPatrascoiu Mihai Anteus Data 6 decembrie 2012 01:06:26
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <stdio.h>
#include <string.h>
#include <vector>
#define N 100005
using namespace std;
vector <int> v[N];
vector <int> u[N];
vector <int> r[N];
int t[N],C[N],sol[N];
int n,m,i,j,componente,S,k;


void citire()
{
	int i,x,y;
	
	scanf ("%d%d", &n,&m);
	
	for (i=1;i<=m;i++)
	{
		scanf ("%d%d", &x,&y);
		v[x].push_back(y);
		u[y].push_back(x);
	}
}

void dfs(int nod, vector <int> v[N], int value)
{
	int i,L=v[nod].size();
	
	t[nod]=1;
	
	for (i=0;i<L;i++)
		if (t[v[nod][i]]==0)
			dfs(v[nod][i], v, value);
		
	if (value==1)
		C[++S]=nod;
	else
		sol[++k]=nod;
}

int main()
{
	freopen ("ctc.in", "r", stdin);
	freopen ("ctc.out", "w", stdout);
	
	citire();
	
	for (i=1;i<=n;i++)
		if (t[i]==0)
			dfs(i,v, 1);
	
	memset (t, 0, sizeof(t));
	
	for (i=S;i>=1;i--)
		if (t[C[i]]==0)
		{
			componente++; k=0;
			dfs(C[i], u, 2);
			
			for (j=1;j<=k;j++)
				r[componente].push_back(sol[j]);
		}
	
	printf ("%d\n", componente);
	for (i=1;i<=componente;i++)
	{
		k=r[i].size();
		for (j=0;j<k;j++)
			printf ("%d ", r[i][j]);
		printf ("\n");
	}
		
	return 0;
}