CS-Notes 图论题解精讲：二分图判定、拓扑排序与并查集实战

本文基于 CS-Notes 仓库中的 [Leetcode 题解 - 图](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/Leetcode 题解 - 图.md?utm_source=gitcode_repo_files) 展开，系统讲解图论算法在面试中的三类核心应用：二分图判定（LeetCode 785）、拓扑排序与课程安排问题（LeetCode 207 / 210）、并查集动态连通性（LeetCode 684）。读完后你可以掌握：用带颜色的 DFS 判定二分图、用后序遍历栈实现拓扑排序及其正确性证明、用并查集在动态连通图中快速定位冗余边，并能结合仓库中 [算法 - 并查集](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/算法 - 并查集.md?utm_source=gitcode_repo_files) 的四种实现对比，理解各并查集变体在 union 与 find 上的复杂度差异。

题集总览

图论部分是 Leetcode 题解系列中"数据结构相关"板块的一个子类（与 链表、树、搜索 等并列）。该系列的选题原则是：从 LeetCode 中精选约 200 道题目，去除繁杂但算法思想含量低的题目，保留面试高频经典题。图论部分收录了 4 道题，覆盖 3 个典型模型：

题号	题目	核心模型	解法
785	Is Graph Bipartite?	二分图判定	带颜色的 DFS 染色
207	Course Schedule	有向图判环	DFS + 全局/局部标记
210	Course Schedule II	拓扑排序	后序遍历 + 栈逆序
684	Redundant Connection	动态连通性	并查集（UF）

一个通用前提：这 4 道题的输入都是"隐式建图"——785 用邻接表数组、207/210 用先修关系列表、684 用边列表。所有代码的时间复杂度都与 V + E（节点数 + 边数）线性相关，下面逐题展开。

二分图

定义

如果可以用两种颜色对图中的节点进行着色，并且保证相邻的节点颜色不同，那么这个图就是二分图。

等价视角：把节点分成两个集合，使得每条边的两端必然落在不同集合中。判定的充要条件是"图中不含奇数长度的环"——奇环无法交替着色。面试中直接写染色法即可，无需先判环。

1. 判断是否为二分图（LeetCode 785）

785. Is Graph Bipartite? (Medium)

示例 1：

Input: [[1,3], [0,2], [1,3], [0,2]]
Output: true
Explanation:
The graph looks like this:
0----1
|    |
|    |
3----2
We can divide the vertices into two groups: {0, 2} and {1, 3}.

示例 2：

Input: [[1,2,3], [0,2], [0,1,3], [0,2]]
Output: false
Explanation:
The graph looks like this:
0----1
| \  |
|  \ |
3----2
We cannot find a way to divide the set of nodes into two independent subsets.

完整解法（原文档实现，DFS 染色）：

public boolean isBipartite(int[][] graph) {
    int[] colors = new int[graph.length];
    Arrays.fill(colors, -1);
    for (int i = 0; i < graph.length; i++) {  // 处理图不是连通的情况
        if (colors[i] == -1 && !isBipartite(i, 0, colors, graph)) {
            return false;
        }
    }
    return true;
}

private boolean isBipartite(int curNode, int curColor, int[] colors, int[][] graph) {
    if (colors[curNode] != -1) {
        return colors[curNode] == curColor;
    }
    colors[curNode] = curColor;
    for (int nextNode : graph[curNode]) {
        if (!isBipartite(nextNode, 1 - curColor, colors, graph)) {
            return false;
        }
    }
    return true;
}

实现要点拆解：

1. 颜色编码：用 int[] colors 记录染色状态，-1 表示未染色，0/1 表示两种颜色。相比 boolean 数组，三态设计可以天然区分"未访问"和"已染色"，避免漏判冲突。
2. 处理非连通图：外层 for 循环对每个未染色节点发起一轮 DFS。若图有多个连通分量，二分性必须对每个分量分别验证，这是本题最常见的遗漏点。
3. 颜色翻转技巧：1 - curColor 用算术而非条件判断完成 0/1 互翻，保证邻居必然与当前节点异色。
4. 提前终止：进入递归时先检查 colors[curNode] != -1——如果该节点已被染色，直接校验它与本次期望颜色是否一致；不一致说明存在奇环，整图不是二分图。
5. 复杂度：每个节点、每条边各被访问常数次，时间复杂度 O(V + E)，额外空间 O(V)。

拓扑排序

拓扑排序常用于在具有先序关系的任务规划中（课程安排、任务调度、依赖构建等）。CS-Notes 选用的实现思路是 DFS 后序遍历 + 栈逆序，而非更常见的入度法（BFS/Kahn 算法）；两种思路在 210 题的正确性上等价，下面先给出判环问题，再给出排序问题。

1. 课程安排的合法性（LeetCode 207）

207. Course Schedule (Medium)

示例：

2, [[1,0]]
return true

2, [[1,0],[0,1]]
return false

题目描述：一个课程可能会有先修课程（注意 prerequisites[i] = [a, b] 表示学 a 之前必须先学 b），判断给定的先修课程规定是否合法。

关键洞察：本题不需要真正产出拓扑序，只需要检测有向图是否存在环即可。有向无环图（DAG）必然存在拓扑排序，反之若存在环则任何先修规定都不合法（环上的课程互为先修，永远无法完成）。

public boolean canFinish(int numCourses, int[][] prerequisites) {
    List<Integer>[] graphic = new List[numCourses];
    for (int i = 0; i < numCourses; i++) {
        graphic[i] = new ArrayList<>();
    }
    for (int[] pre : prerequisites) {
        graphic[pre[0]].add(pre[1]);
    }
    boolean[] globalMarked = new boolean[numCourses];
    boolean[] localMarked = new boolean[numCourses];
    for (int i = 0; i < numCourses; i++) {
        if (hasCycle(globalMarked, localMarked, graphic, i)) {
            return false;
        }
    }
    return true;
}

private boolean hasCycle(boolean[] globalMarked, boolean[] localMarked,
                        List<Integer>[] graphic, int curNode) {

    if (localMarked[curNode]) {
        return true;
    }
    if (globalMarked[curNode]) {
        return false;
    }
    globalMarked[curNode] = true;
    localMarked[curNode] = true;
    for (int nextNode : graphic[curNode]) {
        if (hasCycle(globalMarked, localMarked, graphic, nextNode)) {
            return true;
        }
    }
    localMarked[curNode] = false;
    return false;
}

双标记数组是 DFS 判环的标准做法，其语义是：

• localMarked（局部标记）：节点在当前这条递归路径上。若 DFS 中再次遇到 localMarked[curNode] == true，说明从该节点出发又回到了自身，形成回边，即存在环——这是唯一判环的信号。
• globalMarked（全局标记）：节点已经完整访问过（递归返回后仍保持为 true）。再次遇到全局已标记的节点可以直接剪枝返回 false，避免重复遍历，把总复杂度压到 O(V + E) 而不是 O(V * E)。
• 递归回溯时执行 localMarked[curNode] = false（保留 globalMarked），将节点移出"当前路径"，这是与全局标记配合的关键细节。

建图方向值得注意：graphic[pre[0]].add(pre[1]) 表示从课程 pre[0] 指向其先修 pre[1]（与常规"先修指向后续"的方向相反）。由于判环不依赖边的方向语义（有向图加反边后环依然存在），两种方向都能正确判环。

2. 课程安排的顺序（LeetCode 210）

210. Course Schedule II (Medium)

示例：

4, [[1,0],[2,0],[3,1],[3,2]]
There are a total of 4 courses to take. To take course 3 you should have
finished both courses 1 and 2. Both courses 1 and 2 should be taken after
you finished course 0. So one correct course order is [0,1,2,3].
Another correct ordering is [0,2,1,3].

解法：使用 DFS 实现拓扑排序，用一个栈存储后序遍历结果，这个栈的逆序结果就是拓扑排序结果。

正确性证明（原文档给出）：对于任何先序关系 v -> w，后序遍历保证 w 先于 v 进入栈（w 的后序访问先完成），因此栈的逆序结果中 v 会排在 w 之前，恰好满足"先修在前"的拓扑序要求。

public int[] findOrder(int numCourses, int[][] prerequisites) {
    List<Integer>[] graphic = new List[numCourses];
    for (int i = 0; i < numCourses; i++) {
        graphic[i] = new ArrayList<>();
    }
    for (int[] pre : prerequisites) {
        graphic[pre[0]].add(pre[1]);
    }
    Stack<Integer> postOrder = new Stack<>();
    boolean[] globalMarked = new boolean[numCourses];
    boolean[] localMarked = new boolean[numCourses];
    for (int i = 0; i < numCourses; i++) {
        if (hasCycle(globalMarked, localMarked, graphic, i, postOrder)) {
            return new int[0];
        }
    }
    int[] orders = new int[numCourses];
    for (int i = numCourses - 1; i >= 0; i--) {
        orders[i] = postOrder.pop();
    }
    return orders;
}

private boolean hasCycle(boolean[] globalMarked, boolean[] localMarked, List<Integer>[] graphic,
                         int curNode, Stack<Integer> postOrder) {

    if (localMarked[curNode]) {
        return true;
    }
    if (globalMarked[curNode]) {
        return false;
    }
    globalMarked[curNode] = true;
    localMarked[curNode] = true;
    for (int nextNode : graphic[curNode]) {
        if (hasCycle(globalMarked, localMarked, graphic, nextNode, postOrder)) {
            return true;
        }
    }
    localMarked[curNode] = false;
    postOrder.push(curNode);
    return false;
}

与 207 题的实现相比，增量只有一处：在回溯点（所有邻居遍历完成、退出递归之前）执行 postOrder.push(curNode)。这正是后序遍历的定义位置。几个关键细节：

• 环即失败：只要任意一轮 hasCycle 返回 true，立即返回空数组 new int[0]——有环则不存在合法拓扑序，题目约定此时返回空。
• 逆序出栈：for (int i = numCourses - 1; i >= 0; i--) orders[i] = postOrder.pop(); 依次弹出栈顶填到数组尾部。由于栈底是最早完成的后序节点（依赖链最末端），倒序取出后先修课程自然排在前面的下标位置。
• 无环保证栈满：无环时每个节点恰好入栈一次，栈大小等于 numCourses，orders 一定可以被填满。
• 复杂度：时间 O(V + E)，空间 O(V)（递归栈 + 后序栈 + 标记数组）。

顺带一提：这套 DFS 拓扑序与 Kahn 入度法都能得到合法答案，但两者输出的具体顺序一般不同——拓扑序本身往往不唯一（如示例中 [0,1,2,3] 与 [0,2,1,3] 都合法），题目只要求输出其中一种。

并查集

并查集（Union-Find, UF）用于解决动态连通性问题：可以动态地连通两个点，并且可以非常快速地判断两个点是否连通。它的四个核心操作与复杂度对比，在仓库的 [算法 - 并查集](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/算法 - 并查集.md?utm_source=gitcode_repo_files) 一文中有完整实现（Quick Find、Quick Union、加权 Quick Union、路径压缩的加权 Quick Union），本节先做题目实战，再回头对照该文档做深度拓展。

并查集的核心接口（引自 [算法 - 并查集](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/算法 - 并查集.md?utm_source=gitcode_repo_files)）：

方法	描述
UF(int N)	构造一个大小为 N 的并查集
void union(int p, int q)	连接 p 和 q 节点
int find(int p)	查找 p 所在的连通分量编号
boolean connected(int p, int q)	判断 p 和 q 节点是否连通

1. 冗余连接（LeetCode 684）

684. Redundant Connection (Medium)

示例：

Input: [[1,2], [1,3], [2,3]]
Output: [2,3]
Explanation: The given undirected graph will be like this:
  1
 / \
2 - 3

题目描述：有一系列边连成的图（保证恰好有一个环），找出一条边，移除它之后该图能够成为一棵树。

思路：依次读入边，每读入一条边就查询两端点是否已经连通。若已连通，说明这条边闭合了一个环，它就是要移除的冗余边（题目保证答案存在且是输入中最后造成成环的那条）；若未连通，则执行合并。

public int[] findRedundantConnection(int[][] edges) {
    int N = edges.length;
    UF uf = new UF(N);
    for (int[] e : edges) {
        int u = e[0], v = e[1];
        if (uf.connect(u, v)) {
            return e;
        }
        uf.union(u, v);
    }
    return new int[]{-1, -1};
}

private class UF {

    private int[] id;

    UF(int N) {
        id = new int[N + 1];
        for (int i = 0; i < id.length; i++) {
            id[i] = i;
        }
    }

    void union(int u, v) {
        int uID = find(u);
        int vID = find(v);
        if (uID == vID) {
            return;
        }
        for (int i = 0; i < id.length; i++) {
            if (id[i] == uID) {
                id[i] = vID;
            }
        }
    }

    int find(int p) {
        return id[p];
    }

    boolean connect(int u, v) {
        return find(u) == find(v);
    }
}

实现细节：

1. 下标从 1 开始：本题节点编号为 1 ~ N（N = edges.length），因此 id 数组开 N + 1 并整体初始化，第 0 位留空，避免越界——这与 207/210 中课程编号 0 ~ numCourses-1 不同，是并查集题目的常见坑点。
2. 先查后合：connect 与 union 分离，union 内部还做了一次同分量短路（uID == vID 直接返回），双重防御。
3. 复杂度：从这份源码结构看，find 是 O(1) 的数组直查，而 union 需要遍历整个 id 数组把分量编号全部改写，单次 O(N)——这与 [算法 - 并查集](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/算法 - 并查集.md?utm_source=gitcode_repo_files) 中 Quick Find 变体的设计完全一致（用 union 的线性代价换 find 的常数代价）。本题 N 最多 1000，O(N^2) 的上界足够通过；但若要处理更大规模，应换成下文的高性能变体。

并查集变体对照：从题解实现到仓库完整实现

原文档题解里的 UF 是 Quick Find 形态，而仓库的 [算法 - 并查集](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/算法 - 并查集.md?utm_source=gitcode_repo_files) 给出了完整的演进路线，正好用来回答"union 为什么是 O(N)、能不能更快"：

• Quick Find：保证同一连通分量的所有节点 id 值相等，find 为 O(1)；union 要改写整个分量的编号，代价为 O(N)。题解 684 中的实现即此形态。
• Quick Union：union 只需把一棵树的根指向另一棵树的根，单次 O(1) 级（两次 find 除外）；但 find 要沿 id 指针向上找根，代价与树高成正比，最坏 O(N)。下图展示了连续执行 union(0,3)、union(1,4)、union(0,1) 后森林形态的演化过程（引自 [算法 - 并查集](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/算法 - 并查集.md?utm_source=gitcode_repo_files)）：

• 加权 Quick Union：union 时让小树挂到大树上（维护 sz 数组记录各分量规模），理论上可证明树高不超过 logN，union 与 find 均为 O(logN)。
• 路径压缩的加权 Quick Union：在 find 检查节点的同时将其直接链接到根节点，两者均达到"非常接近 1"的均摊复杂度。

仓库文档给出的复杂度对比表（可直接用于面试口述）：

算法	union	find
Quick Find	N	1
Quick Union	树高	树高
加权 Quick Union	logN	logN
路径压缩的加权 Quick Union	非常接近 1	非常接近 1

其抽象基类设计（id 数组 + connected 模板方法 + 抽象 find/union）与题解 684 中内部类 UF 的接口同构，可以视为同一套接口的"教学版"与"做题版"。

三类模型小结

模型	代表题	关键数据结构	判据/产出
二分图	785	int[] colors（三态染色）	邻节点异色即可着色，注意非连通分量
拓扑排序	207 / 210	邻接表 + 全局/局部双标记	207 只判环；210 后序栈逆序得拓扑序
并查集	684	int[] id 分量编号数组	边端点已连通则该边冗余

三者可以互相迁移：207 的判环 DFS 是通用有向图判环模板；785 的染色 DFS 本质是二分图上的"环长奇偶"检查；684 的并查集则把 DFS 每轮 O(V+E) 的连通性查询摊平到了近似常数。图论题的通用套路就是：先明确图的表示方式（邻接表 / 边列表），再在 DFS/BFS/并查集三种遍历框架中按问题模型选型。更多网格图上的 DFS/BFS 连通性问题（连通分量数目、填充封闭区域等），可参见 Leetcode 题解 - 搜索。