Cod sursa(job #306949)

Utilizator CezarMocanCezar Mocan CezarMocan Data 22 aprilie 2009 14:45:07
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <cstdio>
#include <vector>
#define maxn 100100

using namespace std;

vector <int> g[maxn], gi[maxn];
int n, m, a, b, i, j, nrc, comp;
int st[maxn], sz, viz[maxn];
vector <int> sol[maxn];

void dfp(int nod) {
	int fiu, i;

	if (viz[nod])
		return;
	viz[nod] = 1;

	for (i = 0; i < g[nod].size(); i++) {
		fiu = g[nod][i];
		dfp(fiu);
	}

	sz++;
	st[sz] = nod;

}

void dfm(int nod, int comp) {
	int fiu, i;

	if (viz[nod])
		return;
	viz[nod] = 1;

	sol[comp].push_back(nod);

	for (i = 0; i < gi[nod].size(); i++) {
		fiu = gi[nod][i];
		dfm(fiu, comp);
	}
}

int main() {
	freopen("ctc.in", "r", stdin);
	freopen("ctc.out", "w", stdout);
	
	scanf("%d%d", &n, &m);

	for (i = 1; i <= m; i++) {
		scanf("%d%d", &a, &b);
		g[a].push_back(b);
		gi[b].push_back(a);
	}

	for (i = 1; i <= n; i++)
		dfp(i);

	memset(viz, 0, sizeof(viz));
	
/*	for (i = 1; i <= sz; i++)
		printf("%d ", st[i]);
	printf("\n");*/

	for (i = sz; i > 0; i--) {
		if (!viz[st[i]]) {
			comp++;
			fprintf(stderr, "%d\n", st[i]);
			dfm(st[i], comp);
		}
	}

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


	return 0;
}