冗余连接 图解题解

这道题到底在问什么

输入

edges=[[1,2],[1,3],[2,4],[2,5],[3,6],[3,7],[4,8],[5,9],[6,10],[7,11],[5,2]]

输出

[5,2]

最优解：一步一步想明白

1. 3记住这一句，下面每条边都在套它。
2. 4起手：11 个节点、11 条边。一棵 11 节点的树只该有 11-1=10 条边，这里多了一条——多出来的那条会让图里出现一个环，它就是要找的冗余边。下面逐条加边、揪出成环的那条。
3. 5看边 [1,2]：1 的根是 1，2 的根是 2，根不同 → 这条边接通了两个原本分开的块，安全合并、不成环。
4. 6合并：让根 2 指向根 1，两块并成一块（同色）。连通块数 -1 → 10。
5. 7看边 [1,3]：1 的根是 1，3 的根是 3，根不同 → 这条边接通了两个原本分开的块，安全合并、不成环。
6. 8合并：让根 3 指向根 1，两块并成一块（同色）。连通块数 -1 → 9。
7. 9看边 [2,4]：2 的根是 1，4 的根是 4，根不同 → 这条边接通了两个原本分开的块，安全合并、不成环。
8. 10合并：让根 4 指向根 1，两块并成一块（同色）。连通块数 -1 → 8。
9. 11看边 [2,5]：2 的根是 1，5 的根是 5，根不同 → 这条边接通了两个原本分开的块，安全合并、不成环。
10. 12合并：让根 5 指向根 1，两块并成一块（同色）。连通块数 -1 → 7。
11. 13看边 [3,6]：3 的根是 1，6 的根是 6，根不同 → 这条边接通了两个原本分开的块，安全合并、不成环。
12. 14合并：让根 6 指向根 1，两块并成一块（同色）。连通块数 -1 → 6。
13. 15看边 [3,7]：3 的根是 1，7 的根是 7，根不同 → 这条边接通了两个原本分开的块，安全合并、不成环。
14. 16合并：让根 7 指向根 1，两块并成一块（同色）。连通块数 -1 → 5。
15. 17看边 [4,8]：4 的根是 1，8 的根是 8，根不同 → 这条边接通了两个原本分开的块，安全合并、不成环。
16. 18合并：让根 8 指向根 1，两块并成一块（同色）。连通块数 -1 → 4。
17. 19看边 [5,9]：5 的根是 1，9 的根是 9，根不同 → 这条边接通了两个原本分开的块，安全合并、不成环。
18. 20合并：让根 9 指向根 1，两块并成一块（同色）。连通块数 -1 → 3。
19. 21看边 [6,10]：6 的根是 1，10 的根是 10，根不同 → 这条边接通了两个原本分开的块，安全合并、不成环。
20. 22合并：让根 10 指向根 1，两块并成一块（同色）。连通块数 -1 → 2。
21. 23看边 [7,11]：7 的根是 1，11 的根是 11，根不同 → 这条边接通了两个原本分开的块，安全合并、不成环。
22. 24合并：让根 11 指向根 1，两块并成一块（同色）。连通块数 -1 → 1。
23. 25看边 [5,2]：查根发现 5、2 的根都是 1，它俩在之前的边里早就连通了——再连这条边就把已连通的两点圈成了环。
24. 26两端已同根 → 加上这条边就成环！这条 [5,2] 就是多余的冗余边，正是答案。
25. 27结论：逐条加边时，第一条「两端已经连通」的边 [5,2] 就是冗余边——删掉它，剩下的 10 条边正好连成一棵无环的树（全连成一块、同色）。

⚠️ 容易写错的地方

完整代码（Java / Python / C++）

class Solution {
    int[] parent;
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        parent = new int[n + 1];
        for (int i = 1; i <= n; i++) parent[i] = i;
        for (int[] e : edges) {
            int ra = find(e[0]), rb = find(e[1]);
            if (ra == rb) return e;   // 两端已同根 -> 成环 -> 冗余边
            parent[rb] = ra;
        }
        return new int[0];
    }
    int find(int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    }
}

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        n = len(edges)
        parent = list(range(n + 1))
        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x
        for a, b in edges:
            ra, rb = find(a), find(b)
            if ra == rb:
                return [a, b]   # 两端已同根 -> 成环 -> 冗余边
            parent[rb] = ra
        return []

class Solution {
public:
    vector<int> parent;
    int find(int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    }
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        parent.resize(n + 1);
        for (int i = 1; i <= n; i++) parent[i] = i;
        for (auto& e : edges) {
            int ra = find(e[0]), rb = find(e[1]);
            if (ra == rb) return e;   // 两端已同根 -> 成环 -> 冗余边
            parent[rb] = ra;
        }
        return {};
    }
};

复杂度

面试官可能追问