Re: [閒聊] 每日leetcode

[Rushia (早瀬ユウカの体操服 )]

https://leetcode.com/problems/redundant-connection
684. Redundant Connection
給你一個長度為n的陣列int[][] edges表示邊集合，這些邊組成一個連通圖，求出移除
哪個邊可以讓該圖不存在環且連通，如果答案有多個返回比較後面的邊。

思路:
1.用併查集把edges裡面的邊連通起來，連起來前檢查是不是兩個點在同一組，如果在同
  一組的話就更新res的邊，因為有n個邊和n個點所以必定有解。

Java Code
----------------------------------------------------------------
class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        int[] root = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            root[i] = i;
        }
        int[] res = null;
        for (int[] edge : edges) {
            int a = find(root, edge[0]);
            int b = find(root, edge[1]);
            if (a == b) {
                res = edge;
            }
            root[a] = b;
        }
        return res;
    }

    int find(int[] root, int x) {
        return root[x] == x ? x : (root[x] = find(root, root[x]));
    }
}
----------------------------------------------------------------

--
https://i.imgur.com/O931L58.jpeg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.158.101.161 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1738141093.A.346.html
→ Meaverzt: 大師