建模。课程是顶点，b → a 是有向边（先修指向后修）。「能全部修完」⇔ 存在合法修课顺序 ⇔ 有向图无环。用 Kahn：入度为 0 的课是「随时可修」的，逐门修掉；修不完就是有环。

代码。

#include <vector>
#include <queue>

bool canFinish(int numCourses,
               const std::vector<std::vector<int>>& prereq) {
    std::vector<std::vector<int>> adj(numCourses);
    std::vector<int> indeg(numCourses, 0);
    for (const auto& e : prereq) {          // e = {后修课 a, 先修课 b}
        adj[e[1]].push_back(e[0]);          // 先修 -> 后修
        ++indeg[e[0]];
    }
    std::queue<int> q;
    for (int i = 0; i < numCourses; ++i)
        if (indeg[i] == 0) q.push(i);       // 无先修的课先行
    int taken = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        ++taken;                            // 修掉一门
        for (int v : adj[u])
            if (--indeg[v] == 0) q.push(v); // 该课先修全部满足
    }
    return taken == numCourses;             // 全修完 <=> 无环
}

数值演示。n = 4，prereq = [[1,0],[2,1],[3,2]]（0→1→2→3 一条链）：初始仅 0 入度为 0，依次修 0、1、2、3，taken = 4，返回 true。再补一条 [0,3]（成环 0→1→2→3→0）：四门课入度都为正，队列始终为空，taken = 0，返回 false。

复杂度。建图 \(\Theta(E)\)，Kahn 每顶点入队出队各一次、每条边削一次入度，总 \(\Theta(V + E)\)。空间 \(\Theta(V + E)\)。

边界。无先修（全部入度 0，恒真）；自环先修 [a,a]（a 入度含自环削不掉，正确判假）；n = 1。方向别建反：边的方向只影响「入度」记在谁头上，链路语义要一致。

面试怎么讲。先把「能否修完 ⇔ 有向无环 ⇔ Kahn 能排满」这三个等价讲成一句话，再写代码；主动说明队列为空时的剩余顶点恰是「环上或依赖环」的顶点，判环原理就交代清楚了。

建模。同一张图，这次要真的输出拓扑序，并且用 DFS 版：三色标记同时完成「判环」与「按完成时间倒序收集」两件事——一举覆盖提纲的两个考点。

代码。

#include <vector>
#include <algorithm>

bool dfs(int u, const std::vector<std::vector<int>>& adj,
         std::vector<int>& color, std::vector<int>& order) {
    color[u] = 1;                            // 进栈：灰
    for (int v : adj[u]) {
        if (color[v] == 1) return false;     // 指回当前路径 -> 环
        if (color[v] == 0 && !dfs(v, adj, color, order))
            return false;
    }
    color[u] = 2;                            // 出栈：黑，探明
    order.push_back(u);                      // 记录完成时间
    return true;
}

std::vector<int> findOrder(int n,
                           const std::vector<std::vector<int>>& prereq) {
    std::vector<std::vector<int>> adj(n);
    for (const auto& e : prereq) adj[e[1]].push_back(e[0]);
    std::vector<int> color(n, 0);           // 0 白 1 灰 2 黑
    std::vector<int> order;                 // 完成序（逆序即拓扑序）
    for (int i = 0; i < n; ++i)
        if (color[i] == 0 && !dfs(i, adj, color, order))
            return {};                       // 遇灰色，有环
    std::reverse(order.begin(), order.end());
    return order;
}

数值演示。n = 4，prereq = [[1,0],[2,0],[3,1],[3,2]]：从 0 出发，adj[0] = {1, 2}。先深探 1 → 3（3 无出边，完成入序），1 完成；再探 2 →（3 已黑，跳过）2 完成；0 完成。order = [3,1,2,0]，反转为 [0,2,1,3]——验证每条边：0→1、0→2、1→3、2→3 全部前于终点，合法。

复杂度。\(\Theta(V + E)\)，每顶点染两次、每条边看一次；空间 \(\Theta(V)\)（颜色、序、递归栈）。

边界。有环时中途返回空数组，order 里残留的半成品必须丢弃；n 门课全部无先修时输出任意排列（如 [0,1,...,n-1]）都合法；递归深度最坏 \(\Theta(V)\)，深图可改 Kahn 或显式栈。与例题 1 的关系：把本例「返回空数组」改成「返回 false」就是课程表 I 的 DFS 解，两题同型、仅输出要求不同。

面试怎么讲。讲清 DFS 解的关键不变量「灰色顶点都在当前递归路径上」，以及「最先完成的是汇点、所以完成序要反转」；能同时把 Kahn 与 DFS 两版口径说全，拓扑排序这一节就无懈可击。

建模。邻接表存边（每条无向边存两次），DFS 带父节点：遍历 u 的邻居 v 时，v 等于父节点的这一次是「来的路」要跳过；若还遇到已访问的 v，说明 u 与 v 之间存在第二条路径——环成立。图可能是森林，每个连通块都要起步检查。

代码。

#include <vector>

bool dfsCycle(int u, int parent,
              const std::vector<std::vector<int>>& adj,
              std::vector<bool>& vis) {
    vis[u] = true;
    for (int v : adj[u]) {
        if (v == parent) continue;          // 跳过来的那条边一次
        if (vis[v]) return true;            // 另一条路也到了 v：环
        if (dfsCycle(v, u, adj, vis)) return true;
    }
    return false;
}

bool hasCycleUndirected(int n,
                        const std::vector<std::vector<int>>& edges) {
    std::vector<std::vector<int>> adj(n);
    for (const auto& e : edges) {           // 无向边存两次
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
    }
    std::vector<bool> vis(n, false);
    for (int s = 0; s < n; ++s)             // 森林：逐块检查
        if (!vis[s] && dfsCycle(s, -1, adj, vis))
            return true;
    return false;
}

数值演示。edges = [[0,1],[1,2],[2,0]]：DFS 从 0 出发（父 −1）→ 1（父 0）→ 2（父 1），2 的邻居 1 是父跳过，邻居 0 已访问且非父——环 0-1-2-0 成立，返回 true。去掉 [2,0] 后是一条链，2 的邻居只剩父 1，返回 false。

复杂度。\(\Theta(V + E)\)：每顶点一次访问、每条边两次邻接扫描。空间 \(\Theta(V)\)。

边界。自环 [v,v]：邻接表里 v 出现两次，其中一次会以非父身份命中已访问，正确判环；平行边 [[0,1],[0,1]]：第二条边让 0 在访问 1 后再遇到已访问的 1（父只跳一次），同样正确判环——若声明无重边可省心；空图与单顶点返回 false。并查集变式：逐边 union 前 find，若两端已同集合即环，动态加边场景更顺手。

面试怎么讲。先讲为什么必须跳父节点（无向边天然双向），再给「已访问且非父 ⇔ 两点间已有另一条路 ⇔ 环」这条逻辑链；主动对比有向图三色法，说明「访问过」在两种图里含义不同。

建模。无向图连通分量：对每个未访问顶点启动一次 DFS，启动次数即分量数——与005 章岛屿计数同型（那题是网格版）。有向图强连通分量：Kosaraju 两遍 DFS，第一遍在原图记录完成栈，第二遍在反图按栈序收割 SCC。

代码（无向连通分量计数）。

#include <vector>

void floodFill(int u, const std::vector<std::vector<int>>& adj,
               std::vector<bool>& vis) {
    vis[u] = true;                          // BFS/DFS 均可
    for (int v : adj[u])
        if (!vis[v]) floodFill(v, adj, vis);
}

int countComponents(int n,
                    const std::vector<std::vector<int>>& edges) {
    std::vector<std::vector<int>> adj(n);
    for (const auto& e : edges) {
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
    }
    std::vector<bool> vis(n, false);
    int comps = 0;
    for (int s = 0; s < n; ++s)
        if (!vis[s]) {
            ++comps;                        // 新起点 = 新连通块
            floodFill(s, adj, vis);          // 染尽整块
        }
    return comps;
}

数值演示（无向）。n = 6，edges = [[0,1],[1,2],[3,4]]：块 {0,1,2}、{3,4}、孤点 {5}，答案 3 个分量。经典变体「省份数量」（输入直接是邻接矩阵 isConnected）与本例同型，仅建表方式不同：矩阵里 isConnected[i][j] = 1 就是一条边。

SCC 数值演示（Kosaraju 过程）。有向边 0→1、1→2、2→0、2→3：第一遍 DFS（从 0 出发）：深探 0→1→2，2 的邻居 0 已访问、转 3；3 无出边先完成（栈底压 3），随后 2、1、0 依次完成，栈自底向上为 3, 2, 1, 0。反图边为 1→0、2→1、0→2、3→2。第二遍按「后完成先处理」从栈顶取 0：反图上 0→2→1→0 一趟染尽 {0,1,2}——它们在原图中互达（0→1→2→0），恰是一个 SCC。注意顺序不可反：若错误地从栈底取 3，反图上 3→2→1→0 会把 {3} 也一并染进来，得出错误结果。继续取 1、2 均已访问；取 3 未访问，反图上 3 只到已访问的 2，单节点 SCC {3}。最终两个 SCC：{0,1,2} 与 {3}，缩点后得到分量图 0' → 3'（DAG），可继续拓扑处理。

复杂度。计数版 \(\Theta(V + E)\)。Kosaraju 是两遍完整 DFS 加一次建反图，仍 \(\Theta(V + E)\)、空间 \(\Theta(V + E)\)。

边界。孤立顶点自身是一个连通分量（也是平凡的 SCC）；自环不影响分量划分；n = 0 返回 0。Kosaraju 的易错点在「栈顶先弹」的顺序与「反图上也要查 vis」两处。

面试怎么讲。计数版先讲「启动次数 = 分量数」这一句；SCC 版按「正图记完成序、反图收割」的节奏讲，落点是「缩点后是 DAG，于是可以拓扑/DP」——把 SCC 的用途讲出来，比背算法步骤更能体现理解。