Cod sursa(job #477158)

Utilizator Addy.Adrian Draghici Addy. Data 13 august 2010 17:11:18
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
//O(N^3)

#include <cstdio>
#include <vector>

using namespace std;

#define NMAX 128

int D[NMAX][NMAX], viz[NMAX], n, m, nr_sol;
vector <int> G[NMAX], sol[NMAX];

void read ();
void roy_floyd ();
void DFS ();
void components ();
void print_sol ();

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

void read () {
	
	int i, x, y;
	
	scanf ("%d %d", &n, &m);
	
	for (i = 1; i <= m; i++) {
		scanf ("%d %d", &x, &y);
		D[x][y] = 1;
	}
}

void roy_floyd () {
	
	int k, i, j;
	
	for (k = 1; k <= n; k++)
		for (i = 1; i <= n; i++)
			for (j = 1; j <= n; j++)
				if ((!D[i][j] || D[i][k] + D[k][j] < D[i][j]) && i != j && i != k && k != j && D[i][k] && D[k][j])
					D[i][j] = D[i][k] + D[k][j];
}

void DFS (int nod) {
	
	int i;
	
	viz[nod] = 1; sol[nr_sol].push_back (nod);
	for (i = 1; i < (int) G[nod].size(); i++)
		if (!viz[ G[nod][i] ])
			DFS (G[nod][i]);
}

void components () {
	
	int i, j;
	
	for (i = 2; i <= n; i++)
		for (j = 1; j < i; j++) 
			if (D[i][j] && D[j][i]) {
				G[i].push_back (j);
				G[j].push_back (i);
			}
	
	for (i = 1; i <= n; i++)
		if (!viz[i]) {
			nr_sol++;
			DFS (i);
		}
}

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