Re: [閒聊] 每日leetcode

看板Marginalman作者Rushia (早瀬ユウカの体操服 )時間10月前 (2025/01/29 16:58)推噓0(0推 0噓 1→)

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