Merge pull request #1330 from chubakueno/chubakueno-patch-1

adamant-pwn · web-flow · commit 7c2466d0ab7b · 2024-10-12T02:06:59.000+02:00
Remove components sort, Kosaraju should be O(n)
diff --git a/src/graph/strongly-connected-components.md b/src/graph/strongly-connected-components.md
@@ -119,7 +119,6 @@ void strongly_connected_components(vector<vector<int>> const& adj,
         if (!visited[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)
@@ -139,7 +138,7 @@ The function `dfs` implements depth first search. It takes as input an adjacency
 
 Note that we use the function `dfs` both in the first and second step of the algorithm. In the first step, we pass in the adjacency list of $G$, and during consecutive calls to `dfs`, we keep passing in the same 'output vector' `order`, so that eventually we obtain a list of vertices in increasing order of exit times. In the second step, we pass in the adjacency list of $G^T$, and in each call, we pass in an empty 'output vector' `component`, which will give us one strongly connected component at a time.
 
-When building the adjacency list of the condensation graph, we select the *root* of each component as the first vertex in its sorted list of vertices (this is an arbitrary choice). This root vertex represents its entire SCC. For each vertex `v`, the value `roots[v]` indicates the root vertex of the SCC which `v` belongs to.
+When building the adjacency list of the condensation graph, we select the *root* of each component as the first vertex in its list of vertices (this is an arbitrary choice). This root vertex represents its entire SCC. For each vertex `v`, the value `roots[v]` indicates the root vertex of the SCC which `v` belongs to.
 
 Our condensation graph is now given by the vertices `components` (one strongly connected component corresponds to one vertex in the condensation graph), and the adjacency list is given by `adj_cond`, using only the root vertices of the strongly connected components. Notice that we generate one edge from $C$ to $C'$ in $G^\text{SCC}$ for each edge from some $a\in C$ to some $b\in C'$ in $G$ (if $C\neq C'$). This implies that in our implementation, we can have multiple edges between two components in the condensation graph.
 
