Reachability Analysis
From Any Node, Can You Get Stuck in a Loop?
Some nodes in a directed graph lead to dead ends. Others lead to cycles where you loop forever. Telling them apart requires SCC decomposition followed by reachability analysis on the condensation DAG. This pattern appears in problems about "endless walks," functional graphs, and game-theoretic analysis.
The Core Question
Given a directed graph, for each node u, determine: can u reach a cycle?
A cycle in a directed graph corresponds to an SCC of size >= 2 (or a self-loop). So the question becomes: can node u reach an SCC with a cycle?
Algorithm:
- Find SCCs. Record the size of each SCC.
- Build the condensation DAG.
- Mark each SCC as "has cycle" if its size >= 2 (or it contains a self-loop).
- Reverse-topological DP: SCC c can reach a cycle if it has a cycle itself, or if any of its successors can reach a cycle.
Problem 1: abc245_f — Endless Walk
Problem: N nodes, M directed edges. For each node, can you start there and walk forever without getting stuck? Print the count of such nodes.
Translation: You can walk forever if and only if you can reach a cycle. Once you enter the cycle, you loop indefinitely.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
vector<int> adj[MAXN], radj[MAXN];
int comp[MAXN], sccSz[MAXN];
bool vis[MAXN];
vector<int> order;
void dfs1(int u) {
vis[u] = true;
for (int v : adj[u])
if (!vis[v]) dfs1(v);
order.push_back(u);
}
void dfs2(int u, int c) {
comp[u] = c;
sccSz[c]++;
for (int v : radj[u])
if (comp[v] == -1) dfs2(v, c);
}
int main() {
int n, m;
cin >> n >> m;
bool hasSelfLoop[MAXN] = {};
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
radj[v].push_back(u);
if (u == v) hasSelfLoop[u] = true;
}
for (int i = 1; i <= n; i++)
if (!vis[i]) dfs1(i);
memset(comp, -1, sizeof(comp));
memset(sccSz, 0, sizeof(sccSz));
int numSCC = 0;
for (int i = (int)order.size() - 1; i >= 0; i--)
if (comp[order[i]] == -1)
dfs2(order[i], numSCC++);
// Build condensation DAG
vector<vector<int>> dag(numSCC);
set<pair<int,int>> seen;
for (int u = 1; u <= n; u++)
for (int v : adj[u])
if (comp[u] != comp[v])
if (seen.insert({comp[u], comp[v]}).second)
dag[comp[u]].push_back(comp[v]);
// Check which SCCs have cycles
vector<bool> hasCycle(numSCC, false);
for (int c = 0; c < numSCC; c++)
if (sccSz[c] >= 2) hasCycle[c] = true;
for (int u = 1; u <= n; u++)
if (hasSelfLoop[u]) hasCycle[comp[u]] = true;
// DP: can SCC c reach a cycle?
vector<bool> canReach(numSCC, false);
for (int c = 0; c < numSCC; c++)
if (hasCycle[c]) canReach[c] = true;
// Reverse topological order
for (int c = numSCC - 1; c >= 0; c--)
for (int nc : dag[c])
if (canReach[nc]) canReach[c] = true;
int ans = 0;
for (int i = 1; i <= n; i++)
if (canReach[comp[i]]) ans++;
cout << ans << "\n";
}
Trace on example graph:
Nodes: 1, 2, 3, 4, 5. Edges: 1->2, 2->3, 3->2, 3->4, 4->5.
| Step | Result |
|---|---|
| SCCs | {1} (comp=0), {2,3} (comp=1), {4} (comp=2), {5} (comp=3) |
| SCC sizes | [1, 2, 1, 1] |
| Has cycle | [F, T, F, F] |
| DAG edges | 0->1, 1->2, 2->3 |
| Reverse DP | c=3: F, c=2: F (succ 3 is F), c=1: T (self), c=0: T (succ 1 is T) |
| Can reach cycle | Nodes 1,2,3 -> Yes. Nodes 4,5 -> No. |
| Answer | 3 |
💡 Key insight. Nodes downstream of cycles (reachable FROM a cycle but not reaching any cycle) return false. Only nodes that can reach INTO a cycle count. Direction matters.
Problem 2: abc357_e — Reachability in Functional Graphs
Problem: Each node 1..N has exactly one outgoing edge. Count the total number of (u, v) pairs where u can reach v.
In a functional graph (one outgoing edge per node), every connected component has exactly one cycle with trees hanging off it. But the SCC approach generalizes.
Solution:
- Find SCCs. Each SCC of size k contributes k^2 reachable pairs (everyone reaches everyone).
- Build condensation DAG.
- DP: for each SCC in topological order, count how many nodes are reachable from it. Each SCC c reaches itself (sccSz[c] nodes) plus all nodes reachable from its successors.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
vector<int> adj[MAXN], radj[MAXN];
int comp[MAXN], sccSz[MAXN];
bool vis[MAXN];
vector<int> order;
void dfs1(int u) {
vis[u] = true;
for (int v : adj[u])
if (!vis[v]) dfs1(v);
order.push_back(u);
}
void dfs2(int u, int c) {
comp[u] = c;
sccSz[c]++;
for (int v : radj[u])
if (comp[v] == -1) dfs2(v, c);
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
int v; cin >> v;
adj[i].push_back(v);
radj[v].push_back(i);
}
for (int i = 1; i <= n; i++)
if (!vis[i]) dfs1(i);
memset(comp, -1, sizeof(comp));
memset(sccSz, 0, sizeof(sccSz));
int numSCC = 0;
for (int i = (int)order.size() - 1; i >= 0; i--)
if (comp[order[i]] == -1)
dfs2(order[i], numSCC++);
// Build condensation DAG
vector<vector<int>> dag(numSCC);
for (int u = 1; u <= n; u++)
for (int v : adj[u])
if (comp[u] != comp[v])
dag[comp[u]].push_back(comp[v]);
// DP: reachable[c] = total nodes reachable from SCC c
vector<long long> reach(numSCC, 0);
// Reverse topological order (sinks first)
for (int c = numSCC - 1; c >= 0; c--) {
reach[c] = sccSz[c];
for (int nc : dag[c])
reach[c] += reach[nc];
}
// Total pairs: for each node u, it can reach
// reach[comp[u]] nodes. But nodes within the same
// SCC are counted once per node in the SCC.
// Actually: each node in SCC c contributes reach[c].
long long ans = 0;
for (int i = 1; i <= n; i++)
ans += reach[comp[i]];
cout << ans << "\n";
}
⚠ Gotcha. In a functional graph, each node has exactly one outgoing edge. The condensation DAG also has at most one outgoing edge per SCC (since all nodes in an SCC follow the same path out). This means the condensation is a forest of chains, making the DP trivial. But the general SCC approach works for any directed graph.
Problem 3: abc306_g — Return to 1
Problem: Directed graph. Starting from node 1, can you reach an SCC of size >= 2?
This is the simplest instance of the reachability pattern. Run SCC decomposition, build condensation, check if comp[1] can reach any SCC with size >= 2.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
vector<int> adj[MAXN], radj[MAXN];
int comp[MAXN], sccSz[MAXN];
bool vis[MAXN];
vector<int> order;
void dfs1(int u) {
vis[u] = true;
for (int v : adj[u])
if (!vis[v]) dfs1(v);
order.push_back(u);
}
void dfs2(int u, int c) {
comp[u] = c;
sccSz[c]++;
for (int v : radj[u])
if (comp[v] == -1) dfs2(v, c);
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
radj[v].push_back(u);
}
for (int i = 1; i <= n; i++)
if (!vis[i]) dfs1(i);
memset(comp, -1, sizeof(comp));
memset(sccSz, 0, sizeof(sccSz));
int numSCC = 0;
for (int i = (int)order.size() - 1; i >= 0; i--)
if (comp[order[i]] == -1)
dfs2(order[i], numSCC++);
// Build condensation DAG
vector<vector<int>> dag(numSCC);
set<pair<int,int>> seen;
for (int u = 1; u <= n; u++)
for (int v : adj[u])
if (comp[u] != comp[v])
if (seen.insert({comp[u], comp[v]}).second)
dag[comp[u]].push_back(comp[v]);
// DP: can SCC c reach an SCC of size >= 2?
vector<bool> canReach(numSCC, false);
for (int c = 0; c < numSCC; c++)
if (sccSz[c] >= 2) canReach[c] = true;
for (int c = numSCC - 1; c >= 0; c--)
for (int nc : dag[c])
if (canReach[nc]) canReach[c] = true;
cout << (canReach[comp[1]] ? "Yes" : "No") << "\n";
}
💡 Key insight. "Can node 1 return to itself" is equivalent to "is node 1 in an SCC of size >= 2, or can it reach one and come back?" Actually, returning to node 1 requires node 1 to be IN a cycle, not just reaching one. Re-read the problem carefully. If the problem asks "can node 1 revisit itself," then node 1 must be in an SCC of size >= 2.
The Reachability Pattern
Every problem in this lesson follows the same skeleton:
- SCC decomposition (Kosaraju's or Tarjan's).
- Classify SCCs (has cycle? size >= 2? self-loop?).
- Build condensation DAG.
- DP on the DAG (forward or reverse topological order, depending on whether you need "can reach" or "can be reached from").
| Direction | DP Order | Question Answered |
|---|---|---|
| Forward (u -> v) | Reverse topo (sinks first) | "Can u reach a target?" |
| Backward (v -> u) | Forward topo (sources first) | "Can a target reach u?" |
⚠ Gotcha. "Forward" and "reverse" topological order are easy to confuse. If you want "can node u reach some property downstream," propagate the property backward from sinks to sources. If you want "can some property upstream reach node u," propagate forward from sources to sinks.
Try It
The starter code has Kosaraju's and SCC sizes. Add condensation and reachability DP.
Test case (Endless Walk):
Nodes 1, 2, 3 can reach the cycle {2, 3}. Nodes 4 and 5 cannot.
Test case (Return to 1):
Node 1 is in SCC {1, 2, 3} of size 3. It can return to itself.
Problems
| Problem | Link | Difficulty |
|---|---|---|
| abc245_f — Endless Walk | atcoder.jp/contests/abc245/tasks/abc245_f | Medium |
| abc357_e — Reachability in Functional Graph | atcoder.jp/contests/abc357/tasks/abc357_e | Medium |
| abc306_g — Return to 1 | atcoder.jp/contests/abc306/tasks/abc306_g | Medium |