1. 題目

在本問題中, 樹指的是一個連通且無環(huán)的無向圖。

輸入一個圖，該圖由一個有著N個節(jié)點 (節(jié)點值不重復1, 2, …, N) 的樹及一條附加的邊構成。附加的邊的兩個頂點包含在1到N中間，這條附加的邊不屬于樹中已存在的邊。

結果圖是一個以邊組成的二維數(shù)組。
每一個邊的元素是一對[u, v] ，滿足 u < v，表示連接頂點u 和v的無向圖的邊。

返回一條可以刪去的邊，使得結果圖是一個有著N個節(jié)點的樹。
如果有多個答案，則返回二維數(shù)組中最后出現(xiàn)的邊。
答案邊 [u, v] 應滿足相同的格式 u < v。

示例 1： 輸入: [[1,2], [1,3], [2,3]] 輸出: [2,3] 解釋: 給定的無向圖為:1/ \ 2 - 3示例 2： 輸入: [[1,2], [2,3], [3,4], [1,4], [1,5]] 輸出: [1,4] 解釋: 給定的無向圖為: 5 - 1 - 2| |4 - 3注意: 輸入的二維數(shù)組大小在 3 到 1000。 二維數(shù)組中的整數(shù)在1到N之間，其中N是輸入數(shù)組的大小。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/redundant-connection
著作權歸領扣網(wǎng)絡所有。商業(yè)轉載請聯(lián)系官方授權，非商業(yè)轉載請注明出處。

2. 解題

• 參考 數(shù)據(jù)結構–并查集（Disjoint-Set）

類似題目：
LeetCode 685. 冗余連接 II（并查集）
LeetCode 886. 可能的二分法（著色DFS/BFS/拓展并查集）
LeetCode 990. 等式方程的可滿足性（并查集）
LeetCode 959. 由斜杠劃分區(qū)域（并查集）
LeetCode 1202. 交換字符串中的元素（并查集）
LeetCode 1319. 連通網(wǎng)絡的操作次數(shù)（BFS/DFS/并查集）
程序員面試金典 - 面試題 17.07. 嬰兒名字（并查集）

class dsu {vector<int> f; public:dsu(int n){f.resize(n+1);for(int i = 0; i < n+1; ++i)f[i] = i;}void merge(int a, int b){int fa = find(a), fb = find(b);f[fa] = fb;}int find(int a)//遞歸寫法{if(f[a] == a) return a;return f[a] = find(f[a]);}int find1(int a)//循環(huán)解法{while(a != f[a])a = f[a];return a;}int find2(int a)//循環(huán)+路徑壓縮{int origin = a;while(a != f[a])a = f[a];return f[origin] = a;//路徑壓縮} }; class Solution { public:vector<int> findRedundantConnection(vector<vector<int>>& edges) {dsu u(edges.size());int x, y;for(auto& e : edges){if(u.find(e[0]) != u.find(e[1]))//兩個沒有連接{u.merge(e[0], e[1]);//把邊連接起來}else//已經(jīng)連接了,有環(huán)x = e[0], y = e[1];//記錄下來}return {x,y};} };

12 ms 8.6 MB

總結

以上是生活随笔為你收集整理的LeetCode 684. 冗余连接（并查集）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。