Cod sursa(job #383841)

Utilizator savimSerban Andrei Stan savim Data 18 ianuarie 2010 11:34:25
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <stdio.h>
#include <vector>
#include <string.h>

using namespace std;
    
#define MAX_N 100010

int n, m, p, q, k;
int timp[MAX_N], fol[MAX_N], stiv[MAX_N];
vector <int> G[MAX_N], A[MAX_N], sol[MAX_N];

void dfs(int nod) {
	fol[nod] = 1;

	int len = G[nod].size();
	for (int i = 0; i < len; i++)
		if (!fol[G[nod][i]])
			dfs(G[nod][i]);

	stiv[++stiv[0]] = nod;
}

void tare_conex(int nod) {
    sol[k].push_back(nod);
	
	fol[nod] = 1;

	int len = A[nod].size();
	for (int i = 0; i < len; i++)
		if (!fol[A[nod][i]]) 
			tare_conex(A[nod][i]);
}

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

	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; i++) {
		scanf("%d %d", &p, &q);
		G[p].push_back(q);
		A[q].push_back(p);
	}

	//pasul I : fac df-urile initiale (gen sortare topologica)
	for (int i = 1; i <= n; i++)
		if (!fol[i])
        	dfs(i);
	
	memset(fol, 0, sizeof(fol)); 

	k = 0;
	for (int i = n; i >= 1; i--) 
		if (!fol[stiv[i]]) {
			k++;
	    	tare_conex(stiv[i]);
		}

	printf("%d\n", k);
	for (; k; k--) {
    	int len = sol[k].size();
		for (int i = 0; i < len; i++)
			printf("%d ", sol[k][i]);
		printf("\n");
	}
	             
	return 0;
}