Cod sursa(job #443148)

Utilizator dexter_dexMutascu Adrian - Dragos dexter_dex Data 16 aprilie 2010 09:17:07
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <stdio.h>
#include <vector>
#define Nmax 100005

using namespace std;

int n, m, i, j, x, y, nrc, nr, q;
int S[Nmax];
char viz[Nmax];
vector <int> g[Nmax], t[Nmax], sol[Nmax];

void DFSi (int nod){
	int k;
	viz[nod] = 1;
	for (k = 0 ; k < (int)g[nod].size() ; k++)
		if (viz[g[nod][k]] == 0)
			DFSi(g[nod][k]);
	
	S[++q] = nod;
}

void DFSj(int nod){
	int k;
	viz[nod] = 0;
	sol[nr].push_back(nod);

	for (k = 0 ; k < (int)t[nod].size() ; k++)
		if (viz[t[nod][k]] == 1)
			DFSj(t[nod][k]);
}

int main (){
	freopen ("ctc.in","r", stdin);
	freopen ("ctc.out", "w", stdout);
	
	scanf("%d %d", &n, &m);
	
	for (i = 1 ; i <= m ; i++){
		scanf ("%d %d", &x, &y);
		g[x].push_back(y);
		t[y].push_back(x);
	}
	
	for (i = 1 ; i <= n ; i++)
		if (!viz[i])
			DFSi(i);
	
	for ( ; q > 0 ; q--)
		if (viz[S[q]]){
			nr++;
			DFSj(S[q]);
		}
	
	printf ("%d\n", nr);
	for (i = 1 ; i <= nr ; i++){
		for (j = 0 ; j < (int)sol[i].size() ; j++)
			printf("%d ", sol[i][j]);
		printf("\n");
	}
	
	return 0;
}