Cod sursa(job #2317898)

Utilizator KaryamKaryam Ahmad Karyam Data 13 ianuarie 2019 12:17:22
Problema Componente tare conexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.32 kb
/* Strongly connected components
   A directed graph is strongly connected it there is a path between evey pair of nodes
	 Strongly connected component (SCC) = the maximal strongly connected subgraph

  Kosaraju's algorithm
  --------------------
  1. compute and store the topological sorting of the graph in a stack
  2. compute the transposed graph gt
  3. run DFS on gT from nodes subsequently poped from the stack

  Why it works?
  -------------
  - When you sort the nodes in topological order only the nodes on the left side of one node are accessible from it
  - When you run DFS from nodes poped out of the stack you only traverse the nodes that are still on the stack
  (accessible from the node on the original graph) looking for a path in the reversed way
   This way in a resulting component all the nodes will be accessible from the node and vice versa
  -> there is a path between every two nodes which visits u
*/

#include <bits/stdc++.h>

FILE *fin = freopen("ctc.in", "r", stdin);
FILE *fout = freopen("ctc.out", "w", stdout);

using namespace std;
const int vmax = 1e5+2;

int nodes, edges;
vector <int> g[vmax];
vector <int> gt[vmax];
int visited[vmax];
stack <int> st;
int scc;
vector <int> ans[vmax];

void topologicalSort(int node) {
	visited[node] = true;
	for (int son : g[node])
		if (!visited[son])
			topologicalSort(son);
	st.push(node);
}

void dfs(int node) {
	visited[node] = true;
	ans[scc].push_back(node);

	for (int son : gt[node])
		if (!visited[son])
			dfs(son);
}

void transposeG() {
	for (int i = 1; i <= nodes; ++ i)
		for (int son : g[i])
			gt[son].push_back(i);
}

int main(){
	cin >> nodes >> edges;
	for (int i = 0; i < edges; ++ i) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
	}
	// sort the nodes in topological order
	for (int i = 1; i <= nodes; ++ i)
		if (!visited[i])
			topologicalSort(i);
	// build the transposed graph
	transposeG();
  // initialize the visited nodes
	for (int i = 1; i <= nodes; ++i)
		visited[i] = false;

	while (!st.empty()) {
    int node = st.top();
		st.pop();
		if(!visited[node]){	// compute the scc of node
			dfs(node);
			scc++;
		}
    }

    cout << scc << "\n";
	for (int i = 0; i < scc; ++ i) {
		for (int node : ans[i])
			cout << node << " ";
		cout << "\n";
	}

	return 0;
}