Cod sursa(job #554877)

Utilizator bixcabc abc bixc Data 15 martie 2011 10:13:54
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <cstdio>
#include <list>

using namespace std;

#define NMAX 100050

int S[NMAX], viz[NMAX], N, sol, n;
list <int> G[NMAX], GT[NMAX], CTC[NMAX];

void citire (), kosaraju (), afisare (), DFS1 (int), DFS2 (int);

int main () {
	
	citire ();
	
	kosaraju ();
	
	afisare ();
	
	return 0;
}

void citire () {
	
	freopen ("ctc.in", "r", stdin);
	
	int m, i, x, y;
	
	scanf ("%d %d", &n, &m);
	
	for (i = 1; i <= m; i++) {
		scanf ("%d %d", &x, &y);
		G[x].push_back (y);
		GT[y].push_back (x);
	}
}

void DFS1 (int nod) {
	
	S[++N] = nod, viz[nod] = 1;
	for (list <int>::iterator it = G[nod].begin (); it != G[nod].end (); it++)
		if (!viz[*it])
			DFS1 (*it);
}

void DFS2 (int nod) {
	
	viz[nod] = 0; CTC[sol].push_back (nod);
	for (list <int>::iterator it = GT[nod].begin (); it != GT[nod].end (); it++)
		if (viz[*it])
			DFS2 (*it);
}

void kosaraju () {
	
	for (int i = 1; i <= n; i++)
		if (!viz[i])
			DFS1 (i);
	
	for ( ; N > 0; N--) {
		if (viz[ S[N] ]) {
			sol++;
			DFS2 (S[N]);
		}
	}
}

void afisare () {
	
	freopen ("ctc.out", "w", stdout);
	
	printf ("%d\n", sol);
	
	for (int i = 1; i <= sol; i++) {
		for (list <int>::iterator it = CTC[i].begin (); it != CTC[i].end (); it++)
			printf ("%d ", *it);
		printf ("\n");
	}
}