Cod sursa(job #477175)

Utilizator Addy.Adrian Draghici Addy. Data 13 august 2010 18:05:54
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <cstdio>
#include <vector>

using namespace std;

#define NMAX 100050

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

void read ();
void DFS_1 (int);
void DFS_2 (int);
void kosaraju ();
void print ();

int main () {
	
	freopen ("ctc.in", "r", stdin);
	freopen ("ctc.out", "w", stdout);
	
	read ();
	
	kosaraju ();
	
	print ();
	
	return 0;
}

void read () {
	
	int 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 DFS_1 (int nod) {
	
	int i;
	
	viz[nod] = 1;
	for (i = 0; i < (int) G[nod].size(); i++)
		if (!viz[ G[nod][i] ])
			DFS_1 (G[nod][i]);
	
	S[++N] = nod;
}

void DFS_2 (int nod) {
	
	int i;
	
	viz[nod] = 0; CTC[sol].push_back (nod);
	for (i = 0; i < (int) GT[nod].size(); i++)
		if (viz[ GT[nod][i] ])
			DFS_2 (GT[nod][i]);
}

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

void print () {
	
	int i, j;
	
	printf ("%d\n", sol);
	
	for (i = 1; i <= sol; i++) {
		for (j = 0; j < (int) CTC[i].size(); j++)
			printf ("%d ", CTC[i][j]);
		printf ("\n");
	}
}