Cod sursa(job #497307)

Utilizator vlad_DVlad Dumitriu vlad_D Data 2 noiembrie 2010 04:05:34
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;
int N, M;
vector<vector<int> > G;
vector<vector<int> > C;
stack<int> S;
#define NMAX 100001
int visited[NMAX];
int lowlink[NMAX];
int in_stack[NMAX];
int idx = 0;
void tarjan(int n) {
	visited[n] = lowlink[n] = idx; // set the depth index
	++idx;
	S.push(n);	// push on stack
	in_stack[n] = 1;
	for (int i = 0; i < G[n].size(); ++i) {
		int nod = G[n][i];
		if (!visited[nod]) tarjan(G[n][i]);
		lowlink[n] = min(lowlink[G[n][i]], lowlink[n]);
	}
	if (lowlink[n] == visited[n]) {
		vector<int> aux;
		int nod;
		do {
			nod = S.top(); S.pop();
			aux.push_back(nod);
			in_stack[nod] = 0;
		} while (nod != n);
		C.push_back(aux);
	}
}
int main() {
	freopen("ctc.in", "r", stdin);
	freopen("ctc.out", "w", stdout);
	// reading the graph
	scanf("%d %d", &N, &M);
	G.resize(N+1);
	while (M--) {int x, y; scanf("%d %d", &x, &y); G[x].push_back(y);}

	//Tarjan
	idx = 1;
	for (int i = 1; i <= N; ++i) if (!visited[i]) {
		tarjan(i);
	}
	
	// done
	printf("%d\n", C.size());
	for (int i = 0; i < C.size(); ++i) {
		for (int j = 0; j < C[i].size(); ++j) {
			if (j!=0) printf(" ");
			printf("%d", C[i][j]);
		}
		printf("\n");
	}

	return 0;
}