Cod sursa(job #2668516)

Utilizator Cibotaru.MateiMatei-Stefan Cibotaru Cibotaru.Matei Data 4 noiembrie 2020 23:18:03
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <stack>
#include <set>
#include <algorithm>
using namespace std;

void dfs_topol(vector<list<int>>& graph, vector<bool>& visited, int start, stack<int>& st) {
	for (int i : graph[start]) {
		if (!visited[i]) {
			visited[i] = true;
			dfs_topol(graph, visited, i, st);
		}
	}
	st.push(start);
}

void dfs(vector<list<int>>& graph, vector<bool>& visited, int start, set<int>& component) {
	for (int i : graph[start]) {
		if (!visited[i]) {
			visited[i] = true;
			dfs(graph, visited, i, component);
		}
	}
	component.insert(start);
}

int main()
{
	ifstream fi("ctc.in");
	ofstream fo("ctc.out");

	int m, n;
	
	fi >> n >> m;
	vector<list<int>> graph(n);
	vector<list<int>> inv_graph(n);
	
	for (int i = 0; i < m; i++) {
		int a, b;
		fi >> a >> b;
		a--;
		b--;
		graph[a].push_back(b);
		inv_graph[b].push_back(a);
	}

	vector<bool> visited(n, false);
	stack<int> st;

	for (int i = 0; i < n; i++) {
		if (!visited[i]) {
			dfs_topol(graph, visited, i, st);
		}
	}

	for (int i = 0; i < n; i++) {
		visited[i] = false;
	}

	vector<set<int>> components;
	while (st.size() > 0) {
		int node = st.top();
		st.pop();
		if (!visited[node]) {
			components.push_back(set<int>());
			dfs(inv_graph, visited, node, components.back());
		}
	}

	fo << components.size() << endl;
	for (auto& c : components) {
		for (int i : c) {
			fo << i + 1 << " ";
		}
		fo << endl;
	}

	fi.close();
	fo.close();
	return 0;
}