Cod sursa(job #651325)

Utilizator Addy.Adrian Draghici Addy. Data 20 decembrie 2011 08:26:06
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <cstdio>
#include <vector>

using namespace std;

#define NMAX 100050

bool IN_S[NMAX];
int S[NMAX], niv[NMAX], low[NMAX], N, nr, n, m;
vector <int> CTC[NMAX], G[NMAX];

void tarjan (), dfs (int, int), input (), output ();

int main () {
	
	input ();
	
	tarjan ();
	
	output ();
	
	return 0;
}

void tarjan () {
	
	for (int i = 1; i <= n; i++)
		if (!niv[i])
			dfs (0, i);
}

void dfs (int tata, int nod) {
	
	int fiu, aux;
	vector <int>::iterator it;
	
	low[nod] = niv[nod] = niv[tata] + 1; S[++N] = nod, IN_S[nod] = 1;
	for (it = G[nod].begin (); it != G[nod].end (); it++) {
		fiu = *it;
		if (!niv[fiu]) {
			dfs (nod, fiu);
			low[nod] = min (low[nod], low[fiu]);
		}
		else if (IN_S[fiu])
			low[nod] = min (low[nod], low[fiu]);
	}
	
	if (niv[nod] == low[nod]) {
		nr++;
		do {
			aux = S[N--]; IN_S[aux] = 0;
			CTC[nr].push_back (aux);
		} while (aux != nod);
	}
}

void input () {
	
	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 output () {
	
	freopen ("ctc.out", "w", stdout);
	
	vector <int>::iterator it;
	
	printf ("%d\n", nr);
	
	for (int i = 1; i <= nr; i++) {
		for (it = CTC[i].begin (); it != CTC[i].end (); it++)
			printf ("%d ", *it);
		printf ("\n");
	}
}