Cod sursa(job #1960869)

Utilizator delia_ioanaCeapa Delia Ioana delia_ioana Data 10 aprilie 2017 18:50:51
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include <stdio.h>
#include <vector>
#include <stack>
#include <unordered_set>

using namespace std;

vector<vector<int> > edges, sol;
stack<int> ordered_vertices;
unordered_set<int> visited;

void secondDFS(int node) {
	visited.insert(node);
	sol.back().push_back(node);

	for (auto it : edges[node]) {
		if (visited.find(it) == visited.end()) {
			secondDFS(it);
		}
	}
}

void reverseGraph() {
	vector<vector<int> > reversed_graph;
	vector<int> t;

	for (int i = 0; i < edges.size(); i ++) {
		reversed_graph.push_back(t);
	}

	for (int i = 1; i < edges.size(); i ++) {
		for (int j = 0; j < edges[i].size(); j ++) {
			reversed_graph[edges[i][j]].push_back(i);	
		}
	}

	edges = reversed_graph;
}

void firstDFS(int node) {
	visited.insert(node);

	for (auto it : edges[node]) {
		if (visited.find(it) == visited.end()) {
			firstDFS(it);
		}
	}

	ordered_vertices.push(node);
}


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

	int n, m;

	scanf("%d %d", &n, &m);

	vector<int> t;
	for (int i = 0; i <= n; i ++) {
		edges.push_back(t);
	}

	for (int i = 0; i < m; i ++) {
		int a, b;
		scanf("%d %d", &a, &b);

		edges[a].push_back(b);
	}

	for (int i = 1; i <= n; i ++) {
		if (visited.find(i) == visited.end()) {
			firstDFS(i);
		}
	}

	reverseGraph();
	visited.clear();		

	while (!ordered_vertices.empty()) {
		int node = ordered_vertices.top();
		ordered_vertices.pop();

		if (visited.find(node) == visited.end()) {
			sol.push_back(t);
			secondDFS(node);
		}
	}

	printf("%d\n", sol.size());

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