Cod sursa(job #1460669)

Utilizator mouse_wirelessMouse Wireless mouse_wireless Data 13 iulie 2015 15:03:04
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <list>
#include <vector>
using namespace std;

class graph {
private:
	vector< list<int> > adiac;
public:
	graph(int n) {
		adiac.resize(n);
	}
	int size() {
		return adiac.size();
	}
	const list<int>& neigh(int nod) {
		return adiac[nod];
	}
	void insertEdge(int n1, int n2) {
		adiac[n1].push_back(n2);
	}
	void simpleDFS(int nod, vector<char> &visited, vector<int> &finished) {
		visited[nod] = 1;
		auto L = this->neigh(nod);
		for (auto i = L.begin(); i != L.end(); ++i)
		if (!visited[*i])
			this->simpleDFS(*i, visited, finished);
		finished.push_back(nod);
	}
	void getCompDFS(int nod, vector<char> &visited, vector<int> &ordered) {
		visited[nod] = 1;
		ordered.push_back(nod);
		auto L = this->neigh(nod);
		for (auto i = L.begin(); i != L.end(); ++i)
		if (!visited[*i])
			this->simpleDFS(*i, visited, ordered);
	}
};

int main() {
	freopen("ctc.in", "r", stdin);
	freopen("ctc.out", "w", stdout);
	int N, M;
	scanf("%d %d", &N, &M);
	graph* G = new graph(N);
	graph* revG = new graph(N);
	for (int i = 0; i < M; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		G->insertEdge(a - 1, b - 1);
		revG->insertEdge(b - 1, a - 1);
	}
	vector<int> finished; finished.reserve(N);
	vector<char> visited(N, 0);
	for (int i = 0; i < N; i++)
	if (!visited[i])
		revG->simpleDFS(i, visited, finished);
	delete revG;
	visited.assign(N, 0);
	int nrComp = 0;
	vector<int> orderedNodes; orderedNodes.reserve((N << 1) + 2);
	for (auto i = finished.rbegin(); i != finished.rend(); ++i)
	if (!visited[*i]) {
		nrComp++;
		G->getCompDFS(*i, visited, orderedNodes);
		orderedNodes.push_back(-1);
	}
	printf("%d\n", nrComp);
	for (auto i = orderedNodes.begin(); i != orderedNodes.end(); ++i) {
		if (*i == -1)
			printf("\n");
		else
			printf("%d ", (*i) + 1);
	}
	return 0;
}