题目重点：同一SCC要求互相可达，单向边不是等价关系合并证据。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 节点0..n−1，有向边允许自环；重复添加幂等，删除不存在边幂等。
- 每次components返回当前SCC标签，标签本身不保证跨更新稳定，只比较同组件关系。
解题路线
- 先明确强连通是u能到v且v能到u。DSU适合无向边连通或已知等价合并，不能把每条有向边两端直接union。
- 正确基线用Kosaraju：原图DFS完成次序，反向图按逆完成次序遍历得到SCC。显式DFS iterator栈保留真正递归深搜次序，不能随便把所有邻居标记后当同一完成排序。
- update改变邻接set，查询重算。动态SCC精确优化更复杂；删边可能把一个SCC拆多个，不能以undo一次union代替一般有向删除。
手动走一遍
0→1只有两SCC；加1→0后二者合并；删1→0后重新分开。0→1→2→0三者同SCC，单独3→2不让3也同组，因为不能从前三者返回3。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
class DirectedGraph:
def __init__(self,n):
if n<0:raise ValueError("nonnegative n required")
self.edges=[set() for _ in range(n)]
def update(self,u,v,present):
if not 0<=u<len(self.edges) or not 0<=v<len(self.edges):raise ValueError("invalid vertex")
if present:self.edges[u].add(v)
else:self.edges[u].discard(v)
def components(self):
n=len(self.edges);seen=set();finish=[]
for root in range(n):
if root in seen:continue
seen.add(root);stack=[(root,iter(self.edges[root]))]
while stack:
u,it=stack[-1]
v=next(it,None)
if v is None:stack.pop();finish.append(u)
elif v not in seen:seen.add(v);stack.append((v,iter(self.edges[v])))
reverse=[[] for _ in range(n)]
for u in range(n):
for v in self.edges[u]:reverse[v].append(u)
label=[-1]*n;component=0
for root in reversed(finish):
if label[root]!=-1:continue
label[root]=component;stack=[root]
while stack:
u=stack.pop()
for v in reverse[u]:
if label[v]==-1:label[v]=component;stack.append(v)
component+=1
return label
复杂度
一次update期望O(1)；components O(V+E)时间/空间；Q次查询O(Q(V+E))。大更新量需先说明正确基线与性能目标。
易错点与追问
容易失分的边界
- 把weakly connected与strongly connected混用。
- 只反转边而仍按原节点顺序搜索，不满足Kosaraju完成序条件。
继续深挖
- 仅允许加边时怎样利用SCC缩点DAG检测新增环？
- 需要稳定组件ID时，拆分与合并怎么对外表达？
