Strongly Connected Components
有向图包含 n 个节点，编号从 0 到 n-1，以及一个 edges 列表，其中 [from, to] 表示一条从节点 from 到节点 to 的边。
强连通分量是由一组节点组成的最大集合，其中每个节点都可以沿着边到达其他任意节点。每个节点恰好属于一个分量，不在任何环上的节点单独构成一个分量。返回强连通分量的数量。
函数
- ninteger
- 节点数
- edgesinteger-2d-array
- 有向边，每条边表示为 [from, to]
- 返回值integer
- 强连通分量的数量
约束条件
2 ≤ n ≤ 1041 ≤ edges.length ≤ 5000edges[i] = [from, to]，其中0 ≤ from, to < n且from ≠ to- 没有边会出现两次。
示例
- 输入
- n = 6edges = [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4], [4, 3], [5, 4]]
- 输出
- 3
- 解释
- 节点 0、1 和 2 构成一个循环，因此它们可以相互到达。节点 3 和 4 指向彼此。节点 5 可以到达节点 4，但没有路径返回节点 5，因此它是独立的：共有 3 个连通分量。
- 输入
- n = 5edges = [[1, 0], [0, 1], [2, 3]]
- 输出
- 4
- 解释
- 节点 0 和节点 1 互相指向，构成一个连通分量。从节点 2 到节点 3 的边只有一个方向，因此 2 和 3 是分开的，节点 4 完全没有边：共有 4 个连通分量。
进阶
要让整个图成为一个强连通分量，至少需要添加多少条边？
提示
逐个打开提示，每个都会多透露一点。
当两个节点可以互相到达时，它们恰好属于同一个连通分量。从每个节点开始搜索都能验证这一点，但这样会反复遍历相同的边。一次深度优先搜索能告诉你连通分量从哪里开始吗？
按深度优先搜索首次到达各节点的顺序为它们编号。对每个节点，还要跟踪
low：沿搜索树向下，然后沿一条边回到一个所属连通分量仍未闭合的节点时，能够到达的最小编号。low等于自身编号的节点，就是其连通分量的第一个节点。把已访问的节点保存在栈中。当一个节点完成搜索，且
low等于它自己的编号时，就从栈中弹出节点，直到弹出该节点：这些节点构成一个连通分量，因此将其计数。其中一个测试会让搜索深度达到 5000 个节点，因此请使用自己的（节点，下一个边）帧栈，而不要使用递归。
题解
将每个连通分量缩小为一个点后，这些点就构成了一个无环图。Kosaraju 和 Tarjan 算法利用这一点，在 O(n + E) 时间内找到所有连通分量，其中 E 是边的数量。
从每个节点向前和向后搜索
结果正确，但无法在最大的测试中运行完毕
思路
当节点 u 和 v 能够相互到达时，它们恰好属于同一个连通分量。因此，对于一个尚未属于任何连通分量的节点 s，沿边向前搜索，并沿反向边向后搜索。两次搜索都能找到的节点就是它所属的连通分量。在第一个示例中，从 0 向前搜索会找到 0 到 4，而向后搜索会找到 0、1 和 2，所以 {0, 1, 2} 是一个连通分量。
每个连通分量都需要对图的大部分区域进行两次搜索。在一条经过 5001 个节点、包含 5000 条边的链上，每个节点都各自构成一个连通分量，而搜索会访问约 2.5 × 10^7 个节点。
算法
- 构建每个节点的出边列表和入边列表。
- 取下一个尚未分配到组件的节点
s，并将组件计数加 1。 - 标记从
s沿出边可以到达的节点，以及沿入边可以到达s的节点。 - 两次搜索都标记到的每个节点都加入
s所属的组件。当每个节点都属于某个组件时，返回计数。
def countSCC(n, edges):
out = [[] for _ in range(n)]
rev = [[] for _ in range(n)]
for a, b in edges:
out[a].append(b)
rev[b].append(a)
done = [False] * n
# fwd[v] == s: the search forward from s reached v. bwd[v] == s: v reaches s.
fwd = [-1] * n
bwd = [-1] * n
count = 0
for s in range(n):
if done[s]:
continue
count += 1
# Every node s can reach.
fwd[s] = s
reached = [s]
stack = [s]
while stack:
node = stack.pop()
for nxt in out[node]:
if fwd[nxt] != s:
fwd[nxt] = s
reached.append(nxt)
stack.append(nxt)
# Every node that can reach s.
bwd[s] = s
stack = [s]
while stack:
node = stack.pop()
for prev in rev[node]:
if bwd[prev] != s:
bwd[prev] = s
stack.append(prev)
# The nodes found both ways form the component of s.
for v in reached:
if bwd[v] == s:
done[v] = True
return countKosaraju 算法：两次遍历
思路
在组件图中，有一个汇点，没有边从它出发，从它内部开始搜索时，恰好会找到该组件。Kosaraju 算法安排搜索顺序，让每次搜索都能呈现这样的行为。
第一遍会在每个节点的深度优先搜索结束时将其列出。第二遍在反向图中进行搜索。反向图中的组件相同，搜索从最后结束的节点开始。如果有一条从组件 B 指向组件 C 的边，那么 B 中最后完成的节点会在 C 中的所有节点都完成后才完成。因此，第二遍搜索到 C 时，所有有边指向 C 的组件都已经被标记。在反向图中，搜索无法离开 C。
在第一个示例中，节点的完成顺序是 4、3、2、1、0、5。第二遍依次找到 {5}、{0, 1, 2} 和 {3, 4}。
算法
- 构建出边列表和入边列表。
- 从每个未访问的节点开始进行迭代式深度优先搜索，并在每个节点完成搜索时将其添加到
order。 - 从末尾开始遍历
order。对于每个尚未归入某个分量的节点，将分量计数加 1，并从该节点沿入边搜索，将搜索到的每个未归类节点分配到该分量。返回计数。
def countSCC(n, edges):
out = [[] for _ in range(n)]
rev = [[] for _ in range(n)]
for a, b in edges:
out[a].append(b)
rev[b].append(a)
# Pass 1: depth first search on the graph, listing each node when it finishes.
seen = [False] * n
order = []
for start in range(n):
if seen[start]:
continue
seen[start] = True
# Each frame is [node, next edge to try].
stack = [[start, 0]]
while stack:
frame = stack[-1]
node, i = frame
if i < len(out[node]):
frame[1] += 1
nxt = out[node][i]
if not seen[nxt]:
seen[nxt] = True
stack.append([nxt, 0])
else:
stack.pop()
order.append(node)
# Pass 2: on the reversed graph, start from the last node to finish.
# Each search collects exactly one component.
done = [False] * n
count = 0
for start in reversed(order):
if done[start]:
continue
count += 1
done[start] = True
stack = [start]
while stack:
node = stack.pop()
for prev in rev[node]:
if not done[prev]:
done[prev] = True
stack.append(prev)
return countTarjan 算法：使用 low 值进行一次遍历
思路
运行一次深度优先搜索，并按到达顺序为每个节点编号，称为它的 index。维护一个已访问节点栈，其中存放所属连通分量仍未处理完的节点，并维护一个值 low：它表示从某个节点沿搜索树向下，再沿一条边返回栈中某个节点时，所能到达的最小编号。
当一个节点处理完毕时，如果它的 low 小于 index，说明它下方的某个节点能够返回到更早访问且仍在栈中的节点，所以它会留在栈中。如果两者相等，这个节点就是搜索过程中第一个进入其连通分量的节点：将栈中节点弹出，直到弹出它为止，然后计数加一。指向已弹出节点的边通向一个已经处理完毕、无法返回的连通分量，因此会被忽略。
在第一个示例中，3 会弹出 {4, 3}，0 会弹出 {2, 1, 0}。节点 5 的边指向已经弹出的 4，因此 5 会单独弹出。
算法
- 对于每个未访问的节点，为它分配下一个索引，将
low设为相同的值，将它压入节点栈，并压入帧（节点，第一个边）。 - 如果栈顶帧中的节点还有未处理的边，就沿着这条边继续：未访问的目标节点会获得一个索引并压入一个帧；如果目标节点在节点栈中，则将
low[node]降低为它的索引。 - 否则，弹出该帧，并将父节点的
low降低为low[node]。如果low[node]等于index[node]，就从节点栈中弹出节点，直到弹出该节点，并计数一个连通分量。
def countSCC(n, edges):
out = [[] for _ in range(n)]
for a, b in edges:
out[a].append(b)
index = [-1] * n # discovery time, -1 while unvisited
low = [0] * n # earliest discovery time the node can reach and still return from
on_stack = [False] * n
stack = [] # visited nodes whose component is still open
time = 0
count = 0
for start in range(n):
if index[start] != -1:
continue
index[start] = low[start] = time
time += 1
stack.append(start)
on_stack[start] = True
# The depth first search keeps its own call stack: [node, next edge to try].
calls = [[start, 0]]
while calls:
frame = calls[-1]
node, i = frame
if i < len(out[node]):
frame[1] += 1
nxt = out[node][i]
if index[nxt] == -1:
index[nxt] = low[nxt] = time
time += 1
stack.append(nxt)
on_stack[nxt] = True
calls.append([nxt, 0])
elif on_stack[nxt]:
# An edge back into an open component.
low[node] = min(low[node], index[nxt])
else:
calls.pop()
if calls:
parent = calls[-1][0]
low[parent] = min(low[parent], low[node])
# Nothing below node reaches above it: node closes a component.
if low[node] == index[node]:
count += 1
while True:
w = stack.pop()
on_stack[w] = False
if w == node:
break
return count
易错点和边界情况
- 忘记了没有边的节点。在第二个示例中，节点 4 没有出现在任何边中，但它仍然是一个强连通分量。
- 通过任何已访问的节点降低
low，而不是只通过栈中的节点。在第一个示例中，边5 → 4会让 5 无法结束自己的强连通分量。 - 把边当作双向边处理。这样算出的是连通分量：第一个示例会得到 1，而不是 3。
- 在 Python 中使用递归。经过 5000 个节点的环会嵌套 5000 次调用，是默认限制 1000 的 5 倍。请自行维护一个调用帧栈。
- 在原始边上运行 Kosaraju 算法的第二遍，或者按照节点首次访问的顺序运行。无论哪种做法，都会合并只能单向到达彼此的分量。
常见问题3
查找强连通分量的时间复杂度是多少？
使用 Kosaraju 或 Tarjan 算法时，时间复杂度为 O(n + E)，因为每个节点和边都会被处理常数次。两种算法都需要 O(n + E) 的空间来存储边列表和搜索栈。
你应该使用 Kosaraju 算法还是 Tarjan 算法？
Kosaraju 算法由两次普通搜索组成，不容易出错。Tarjan 算法只需要一次搜索，也不需要反向图，但要维护 low。
强连通分量和连通分量有什么区别？
连通分量不考虑边的方向：只要存在一条路径连接两个节点，它们就属于同一个连通分量。强连通分量要求每个节点都能到达其他节点。第一个示例中有一个连通分量，但有三个强连通分量。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def countSCC(n, edges):
# 在这里编写代码测试 #1
测试 #2
参数
n = 6 edges = [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4], [4, 3], [5, 4]]
预期输出
3