Cod sursa(job #2926651)

Utilizator RaduAntoneoAntonio Alexandru Radu RaduAntoneo Data 18 octombrie 2022 11:40:01
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>
using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");
#define cin f
#define cout g

vector<vector<int>> adj, trans;
stack<int> st;
vector<bool> visited;

void topoSort(int currNode) {
	visited[currNode] = 1;

	for (int x : adj[currNode])
		if (!visited[x])
			topoSort(x);

	st.push(currNode);
}

void DFS(int currNode, vector<int> &sol) {
	visited[currNode] = 1;

	for (int x : trans[currNode])
		if (!visited[x])
			DFS(x, sol);

	sol.push_back(currNode);
}

int main() {
	int n, m;
	cin >> n >> m;

	adj.resize(n+1);
	trans.resize(n+1);
	visited.resize(n+1);

	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		trans[v].push_back(u);
	}

	for (int i = 1; i <= n; i++) 
		if (!visited[i])
			topoSort(i);

	fill(visited.begin(), visited.end(), 0);
	int countCTC = 0;
	vector<vector<int>> finalSol;

	while (!st.empty()) {
		int currNode = st.top();
		st.pop();

		if (!visited[currNode]) {
			countCTC++;
			vector<int> sol;
			DFS(currNode, sol);
			finalSol.push_back(sol);
		}
	}
	cout << countCTC << '\n';
	for (auto vec : finalSol) {
		for (int x : vec)
			cout << x << " ";
		cout << '\n';
	}

	return 0;
}