Cod sursa(job #1893542)

Utilizator preda.andreiPreda Andrei preda.andrei Data 25 februarie 2017 19:17:51
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include <algorithm>
#include <fstream>
#include <vector>

#include <iostream>

using namespace std;

typedef vector<vector<int>> Graph;

void Dfs(const Graph &g, int node, vector<bool> &vis, vector<int> &ord)
{
	vis[node] = true;
	for (int i : g[node]) {
		if (!vis[i]) {
			Dfs(g, i, vis, ord);
		}
	}
	ord.push_back(node);
}

vector<int> TopoSort(const Graph &g)
{
	vector<bool> visited(g.size(), false);
	vector<int> order;

	for (unsigned i = 0; i < g.size(); ++i) {
		if (!visited[i]) {
			Dfs(g, i, visited, order);
		}
	}
	return order;
}

void Fill(const Graph &g, vector<int> &colours, int node, int col)
{
	colours[node] = col;
	for (int i : g[node]) {
		if (colours[i] == -1) {
			Fill(g, colours, i, col);
		}
	}
}

vector<vector<int>> FindComponents(const Graph &norm, const Graph &rev)
{	
	auto order = TopoSort(norm);

	vector<int> colours(norm.size(), -1);
	int ncolours = 0;

	for (int i = order.size() - 1; i >= 0; --i) {
		if (colours[order[i]] == -1) {
			Fill(rev, colours, order[i], ncolours);
			++ncolours;
		}
	}

	vector<vector<int>> components(ncolours);
	for (unsigned i = 0; i < colours.size(); ++i) {
		components[colours[i]].push_back(i);
	}
	return components;
}

int main()
{
	ifstream fin("ctc.in");
	ofstream fout("ctc.out");

	int n, m;
	fin >> n >> m;

	Graph normal_graph(n);
	Graph reversed_graph(n);
	while (m--) {
		int x, y;
		fin >> x >> y;
		normal_graph[x - 1].push_back(y - 1);
		reversed_graph[y - 1].push_back(x - 1);
	}

	auto comp = FindComponents(normal_graph, reversed_graph);
	fout << comp.size() << "\n";
	for (const auto &c : comp) {
		for (int i : c) {
			fout << i + 1 << " ";
		}
		fout << "\n";
	}

	return 0;
}