并查集与拓扑排序

并查集用于处理集合的合并与查询，常用于连通分量、冗余连接等问题。拓扑排序用于有向无环图（DAG）的排序，常用于任务调度、课程安排等。

典型例题

1. 冗余连接（并查集）

def findRedundantConnection(edges):
    parent = list(range(len(edges)+1))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    for u, v in edges:
        pu, pv = find(u), find(v)
        if pu == pv:
            return [u, v]
        parent[pu] = pv
print(findRedundantConnection([[1,2],[1,3],[2,3]]))  # 输出: [2,3]

2. 课程表（拓扑排序）

from collections import deque
def canFinish(numCourses, prerequisites):
    indegree = [0]*numCourses
    graph = [[] for _ in range(numCourses)]
    for a, b in prerequisites:
        graph[b].append(a)
        indegree[a] += 1
    queue = deque([i for i in range(numCourses) if indegree[i]==0])
    count = 0
    while queue:
        node = queue.popleft()
        count += 1
        for nei in graph[node]:
            indegree[nei] -= 1
            if indegree[nei] == 0:
                queue.append(nei)
    return count == numCourses
print(canFinish(2, [[1,0]]))  # 输出: True