Cod sursa(job #477409)

Utilizator Addy.Adrian Draghici Addy. Data 14 august 2010 14:48:48
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define NMAX 100050

int S[NMAX], S_viz[NMAX], idx[NMAX], low[NMAX], n, m, nr_ctc, index, N;
vector <int> G[NMAX], CTC[NMAX];

void citire ();
void ctc ();
void tarjan (int);
void afisare ();

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

void citire () {
	
	freopen ("ctc.in", "r", stdin);
	
	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);
	}
}

void ctc () {
	
	int i;
	
	for (i = 1; i <= n; i++)
		if (!idx[i])
			tarjan (i);
}

void tarjan (int nod) {
	
	int i, fiu, aux;
	
	index++;
	idx[nod] = index, low[nod] = index;
	
	S[++N] = nod, S_viz[nod] = 1;
	
	for (i = 0; i < (int) G[nod].size(); i++) {
		fiu = G[nod][i];
		if (!idx[fiu]) {
			tarjan (fiu);
			low[nod] = min (low[nod], low[fiu]);
		}
		else if (S_viz[fiu])
			low[nod] = min (low[nod], low[fiu]);
	}
	
	if (idx[nod] == low[nod]) {
		nr_ctc++;
		do {
			aux = S[N--], S_viz[aux] = 0;
			CTC[nr_ctc].push_back (aux);
		} while (aux != nod);
	}
}

void afisare () {
	
	freopen ("ctc.out", "w", stdout);
	
	int i, j;
	
	printf ("%d\n", nr_ctc);
	
	for (i = 1; i <= nr_ctc; i++) {
		for (j = 0; j < (int) CTC[i].size(); j++)
			printf ("%d ", CTC[i][j]);
		printf ("\n");
	}
}