Cod sursa(job #1427878)

Utilizator nytr0gennytr0gen nytr0gen Data 3 mai 2015 11:13:24
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <iostream>
#include <vector>
#include <list>

using namespace std;

const int NMAX = 100000;
struct {
	vector<int> vecini;
	bool vizitat = false;
} graf[NMAX], grafT[NMAX];

list<int> fin;
vector<int> results[NMAX];

void dfs(int v) {
	graf[v].vizitat = true;
	for (const int u: graf[v].vecini) {
		if (!graf[u].vizitat) {
			dfs(u);
		}
	}

	fin.push_front(v);
}

void dfsT(int v, int comp) {
	grafT[v].vizitat = true;
	for (const int u: grafT[v].vecini) {
		if (!grafT[u].vizitat) {
			dfsT(u, comp);
		}
	}

	results[comp].push_back(v);
}

int main() {
	freopen("ctc.in", "r", stdin);
	freopen("ctc.out", "w", stdout);

	int N, M; scanf("%d %d\n", &N, &M);
	while (M--) {
		int v, u; scanf("%d %d\n", &v, &u);
		graf[v].vecini.push_back(u);
		grafT[u].vecini.push_back(v);
	}

	for (int v = 1; v <= N; v++) {
		if (!graf[v].vizitat) {
			dfs(v);
		}
	}

	int comp = 0;
	for (const int v: fin) {
		if (!grafT[v].vizitat) {
			dfsT(v, comp++);
		}
	}

	printf("%d\n", comp);
	while (comp--) {
		for (const int v: results[comp]) {
			printf("%d ", v);
		}
		printf("\n");
	}

	return 0;
}