拓扑排序与并查集

拓扑排序

只适用于有向无环图（DAG），用于表示任务依赖顺序。

BFS（Kahn 算法，推荐）

int[] topoSort(int n, int[][] edges) {
    List<List<Integer>> graph = new ArrayList<>();
    int[] inDegree = new int[n];
    for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
    for (int[] e : edges) {
        graph.get(e[0]).add(e[1]);
        inDegree[e[1]]++;
    }
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < n; i++) if (inDegree[i] == 0) queue.offer(i);
    int[] order = new int[n]; int idx = 0;
    while (!queue.isEmpty()) {
        int u = queue.poll();
        order[idx++] = u;
        for (int v : graph.get(u)) {
            if (--inDegree[v] == 0) queue.offer(v);
        }
    }
    return idx == n ? order : new int[]{};  // idx < n 说明有环
}

DFS（后序反转）

int[] color;  // 0=未访问, 1=访问中, 2=已完成
List<Integer> result;
boolean hasCycle;

boolean dfs(int u) {
    color[u] = 1;  // 标记访问中
    for (int v : graph.get(u)) {
        if (color[v] == 1) { hasCycle = true; return false; }
        if (color[v] == 0 && !dfs(v)) return false;
    }
    color[u] = 2;
    result.add(u);  // 后序加入（最终需要 reverse）
    return true;
}

应用：课程安排（LeetCode 207 / 210）

boolean canFinish(int n, int[][] prerequisites) {
    // 直接用 Kahn 算法，判断 idx == n
    return topoSort(n, prerequisites).length == n;
}

并查集（Union-Find）

高效处理集合合并与查找，常用于判断连通性。

class UnionFind {
    int[] parent, rank;

    UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    // 路径压缩
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    // 按秩合并
    boolean union(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;  // 已在同一集合
        if (rank[px] < rank[py]) { int tmp = px; px = py; py = tmp; }
        parent[py] = px;
        if (rank[px] == rank[py]) rank[px]++;
        return true;
    }

    boolean connected(int x, int y) { return find(x) == find(y); }
}

应用：朋友圈数量（LeetCode 547）

int findCircleNum(int[][] isConnected) {
    int n = isConnected.length;
    UnionFind uf = new UnionFind(n);
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (isConnected[i][j] == 1) uf.union(i, j);
    int count = 0;
    for (int i = 0; i < n; i++) if (uf.find(i) == i) count++;
    return count;
}

应用：冗余连接（LeetCode 684）

加边时若两端已连通，则该边为冗余：

int[] findRedundantConnection(int[][] edges) {
    UnionFind uf = new UnionFind(edges.length + 1);
    for (int[] e : edges) {
        if (!uf.union(e[0], e[1])) return e;
    }
    return new int[]{};
}

最小生成树（Kruskal）

将并查集与贪心结合，权重从小到大加边：

int minCostConnectPoints(int[] x, int[] y) {
    int n = x.length;
    // 生成所有边并按权重排序
    List<int[]> edges = new ArrayList<>();
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            edges.add(new int[]{Math.abs(x[i]-x[j]) + Math.abs(y[i]-y[j]), i, j});
    edges.sort(Comparator.comparingInt(e -> e[0]));
    UnionFind uf = new UnionFind(n);
    int cost = 0, count = 0;
    for (int[] e : edges) {
        if (uf.union(e[1], e[2])) { cost += e[0]; if (++count == n - 1) break; }
    }
    return cost;
}