change code to use single dfs function (adamant-pwn's suggestion) and create test

el-sambal · el-sambal · commit 5ef11997d412 · 2024-07-15T05:09:49.000+02:00
diff --git a/src/graph/strongly-connected-components.md b/src/graph/strongly-connected-components.md
@@ -72,72 +72,66 @@ The runtime complexity of the algorithm is $O(n + m)$, because depth first searc
 Finally, it is appropriate to mention [topological sort](topological-sort.md) here. In step 2, the algorithm finds strongly connected components in decreasing order of their exit times. Thus, it finds components - vertices of the condensation graph - in an order corresponding to a topological sort of the condensation graph.
 
 ## Implementation
-```cpp
-vector<vector<int>> adj, adj_rev; // adjacency lists of G and G^T
-vector<bool> visited;             // keeps track of which nodes are already visited
-vector<int> order;                // sorted list of G's vertices by exit time
-vector<int> component;            // stores one strongly connected component at a time
- 
-void dfs1(int v) {
+```{.cpp file=strongly_connected_components}
+vector<bool> visited; // keeps track of which nodes are already visited
+
+// runs depth first search starting at vertex v.
+// each visited vertex is appended to the output vector when dfs leaves it.
+void dfs(int v, vector<vector<int>> &adj, vector<int> &output) {
     visited[v] = true;
     for (auto u : adj[v])
         if (!visited[u])
-            dfs1(u);
-
-    order.push_back(v);
+            dfs(u, adj, output);
+    output.push_back(v);
 }
- 
-void dfs2(int v) {
-    visited[v] = true;
-    component.push_back(v);
 
-    for (auto u : adj_rev[v])
-        if (!visited[u])
-            dfs2(u);
-}
- 
-int main() {
-    int n = ...; 
-    for ( ... ) {
-        int a = ..., b = ...;
-        adj[a].push_back(b);
-        adj_rev[b].push_back(a);
-    }
- 
+// input: adj -- adjacency list of G
+// output: components -- the strongy connected components in G
+// output: adj_scc -- adjacency list of G^SCC (by root nodes)
+void strongy_connected_components(vector<vector<int>> &adj,
+                                  vector<vector<int>> &components,
+                                  vector<vector<int>> &adj_scc) {
+    int n = adj.size();
+    components.clear(), adj_scc.clear();
+
+    // create adjacency list of G^T
+    vector<vector<int>> adj_rev(n);
+    for (int v = 0; v < n; v++)
+        for (int u : adj[v])
+            adj_rev[u].push_back(v);
+
+    vector<int> order; // will be a sorted list of G's vertices by exit time
+
     visited.assign(n, false);
 
     // first series of depth first searches
     for (int i = 0; i < n; i++)
         if (!visited[i])
-            dfs1(i);
+            dfs(i, adj, order);
 
     visited.assign(n, false);
     reverse(order.begin(), order.end());
 
-    // condensation graph (explained in text below)
-    vector<int> root_nodes;
-    vector<int> roots(n, 0);
-    vector<vector<int>> adj_scc(n);
-    
+    vector<int> roots(n, 0); // gives the root vertex of a vertex's SCC
+
     // second series of depth first searches
     for (auto v : order)
         if (!visited[v]) {
-            dfs2(v);
+            std::vector<int> component;
+            dfs(v, adj_rev, component);
+            sort(component.begin(), component.end());
+            components.push_back(component);
             int root = component.front();
-            for (auto u : component) roots[u] = root;
-            root_nodes.push_back(root);
-            component.clear();
+            for (auto u : component)
+                roots[u] = root;
         }
-    
-    
+
     // add edges to condensation graph
+    adj_scc.assign(n, {});
     for (int v = 0; v < n; v++)
         for (auto u : adj[v])
             if (roots[v] != roots[u])
                 adj_scc[roots[v]].push_back(roots[u]);
-
-    // finished finding SCCs and constructing condensation graph.
-    .......
 }
 ```
 
diff --git a/test/test_strongly_connected_components.cpp b/test/test_strongly_connected_components.cpp
@@ -0,0 +1,50 @@
+#include <bits/stdc++.h>
+using namespace std;
+
+#include "strongly_connected_components.h"
+
+int main() {
+    // we only have a single test case for now
+    int n = 10;
+    vector<vector<int>> adj(n);
+    adj[0].push_back(1);
+    adj[0].push_back(7);
+    adj[1].push_back(1);
+    adj[1].push_back(2);
+    adj[2].push_back(1);
+    adj[2].push_back(5);
+    adj[3].push_back(2);
+    adj[3].push_back(4);
+    adj[4].push_back(9);
+    adj[5].push_back(3);
+    adj[5].push_back(6);
+    adj[5].push_back(9);
+    adj[6].push_back(2);
+    adj[7].push_back(0);
+    adj[7].push_back(6);
+    adj[7].push_back(8);
+    adj[8].push_back(6);
+    adj[8].push_back(9);
+    adj[9].push_back(4);
+
+    vector<vector<int>> components, adj_scc;
+    strongy_connected_components(adj, components, adj_scc);
+
+    // sort things to make it easier to verify
+    sort(components.begin(), components.end(),
+         [](auto &l, auto &r) { return l[0] < r[0]; });
+    for (vector<int> a : adj_scc)
+        sort(a.begin(), a.end());
+
+    assert(components.size() == 4);
+    assert(components[0] == std::vector<int>({0, 7}));
+    assert(components[1] == std::vector<int>({1, 2, 3, 5, 6}));
+    assert(components[2] == std::vector<int>({4, 9}));
+    assert(components[3] == std::vector<int>({8}));
+
+    assert(adj_scc[0] == std::vector<int>({1, 1, 8}));
+    assert(adj_scc[1] == std::vector<int>({4, 4}));
+    assert(adj_scc[8] == std::vector<int>({1, 4}));
+
+    return 0;
+}
