SCC (Tarjan)
O(n + m)Strongly connected components in one DFS with lowlink values and an explicit stack. Component ids come out in reverse topological order (the opposite of the Kosaraju template). Recursive: raise the stack limit for large inputs, or use the Kosaraju template, which is iterative.
// use it on
CSES: Flight Routes Check ↗
All cities mutually reachable means exactly one SCC. Run either SCC template and check comps == 1.
// the code
struct TarjanSCC { // comp ids in reverse topological order
int n, timer = 0, comps = 0;
vector<vector<int>> adj;
vector<int> tin, low, comp, st;
vector<bool> onstack;
TarjanSCC(int n)
: n(n), adj(n), tin(n, -1), low(n), comp(n, -1), onstack(n, false) {}
void add_edge(int u, int v) { adj[u].push_back(v); }
void dfs(int u) {
tin[u] = low[u] = timer++;
st.push_back(u);
onstack[u] = true;
for (int v : adj[u]) {
if (tin[v] == -1) {
dfs(v);
low[u] = min(low[u], low[v]);
} else if (onstack[v]) {
low[u] = min(low[u], tin[v]);
}
}
if (low[u] == tin[u]) { // u is the root of an SCC
while (true) {
int v = st.back();
st.pop_back();
onstack[v] = false;
comp[v] = comps;
if (v == u) break;
}
comps++;
}
}
void run() {
for (int u = 0; u < n; u++)
if (tin[u] == -1) dfs(u);
}
};// more connectivity