Cod sursa(job #2704367)

Utilizator razvan9310FMI - Razvan Damachi razvan9310 Data 10 februarie 2021 14:12:08
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.96 kb
#include <bits/stdc++.h>
using namespace std;

int dfs_1(const int root,
		  const vector<vector<int>>& g,
		  vector<pair<int, int>>& f) {
	f[root].second = 0;
	int adj_time = 0;
	for (const int adj : g[root]) {
		if (f[adj].second == -1) {
			adj_time = max(adj_time, dfs_1(adj, g, f));
		}
	}
	f[root].second = adj_time + 1;
	return f[root].second;
}

void dfs_2(const int root,
           const vector<vector<int>>& g,
           vector<int>& sccs,
           const int curr_scc) {
	sccs[root] = curr_scc;
	for (const int adj : g[root]) {
		if (sccs[adj] == -1) {
			dfs_2(adj, g, sccs, curr_scc);
		}
	}
}

vector<int> compute_sccs(const int n, const vector<vector<int>>& g) {
	vector<pair<int, int>> f(n + 1);
	for (int i = 1; i <= n; ++i) {
		f[i] = make_pair(i, -1);
	}
	for (int i = 1; i <= n; ++i) {
		if (f[i].second == -1) {
			dfs_1(i, g, f);
		}
	}
	
	vector<vector<int>> gt(n + 1);
	for (int i = 1; i <= n; ++i) {
		for (const int adj : g[i]) {
			gt[adj].push_back(i);
		}
	}
	
	auto cmp = [](const pair<int, int>& x, const pair<int, int>& y) {
		return x.second > y.second;
	};
	sort(f.begin(), f.end(), cmp);
	vector<int> sccs(n + 1, -1);
	int next_scc = 1;
	for (const pair<int, int>& p : f) {
		if (p.first > 0 && sccs[p.first] == -1) {
			dfs_2(p.first, gt, sccs, next_scc);
			++next_scc;
		}
	}
	
	return sccs;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	ifstream in("ctc.in");
	in.tie(nullptr);
	ofstream out("ctc.out");
	out.tie(nullptr);
	
	int n, m;
	in >> n >> m;
	vector<vector<int>> g(n + 1);
	for (int i = 0; i < m; ++i) {
		int u, v;
		in >> u >> v;
		g[u].push_back(v);
	}
	
	vector<int> sccs = compute_sccs(n, g);
	unordered_map<int, vector<int>> scc_to_node;
	for (int i = 1; i <= n; ++i) {
		scc_to_node[sccs[i]].push_back(i);
	}
	out << scc_to_node.size() << "\n";
	for (auto map_it = scc_to_node.begin(); map_it != scc_to_node.end();
	     ++map_it) {
		for (const int node : map_it->second) {
			out << node << " ";
		}
		out << "\n";
	}
}