Cod sursa(job #2668616)

Utilizator Cibotaru.MateiMatei-Stefan Cibotaru Cibotaru.Matei Data 5 noiembrie 2020 04:19:49
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.6 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) {
	visited[start] = true;
	for (int i : graph[start]) {
		if (!visited[i]) {
			dfs_topol(graph, visited, i, st);
		}
	}
	st.push(start);
}

void dfs(vector<list<int>>& graph, vector<bool>& visited, int start, vector<int>& component) {
	visited[start] = true;
	for (int i : graph[start]) {
		if (!visited[i]) {
			dfs(graph, visited, i, component);
		}
	}
	component.push_back(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<int> *components = new vector<int>[n];
	int top = 0;
	while (st.size() > 0) {
		int node = st.top();
		st.pop();
		if (!visited[node]) {
			dfs(inv_graph, visited, node, components[top]);
			top++;
		}
	}

	fo << top << endl;
	for (int c = 0; c < top; c++) {
		sort(components[c].begin(), components[c].end());
		for (int i : components[c]) {
			fo << i + 1 << " ";
		}
		fo << endl;	
	}

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