Pagini recente » Cod sursa (job #27450) | Cod sursa (job #2156971) | Cod sursa (job #1609727) | Cod sursa (job #3350476) | Cod sursa (job #2317898)
/* 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;
}