1. 題目

在本問題中，有根樹指滿足以下條件的有向圖。該樹只有一個根節點，所有其他節點都是該根節點的后繼。
每一個節點只有一個父節點，除了根節點沒有父節點。

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

結果圖是一個以邊組成的二維數組。 每一個邊 的元素是一對 [u, v]，用以表示有向圖中連接頂點 u and v和頂點的邊，其中父節點u是子節點v的一個父節點。

返回一條能刪除的邊，使得剩下的圖是有N個節點的有根樹。
若有多個答案，返回最后出現在給定二維數組的答案。

示例 1: 輸入: [[1,2], [1,3], [2,3]] 輸出: [2,3] 解釋: 給定的有向圖如下:1/ \ v v 2-->3示例 2: 輸入: [[1,2], [2,3], [3,4], [4,1], [1,5]] 輸出: [4,1] 解釋: 給定的有向圖如下: 5 <- 1 -> 2^ || v4 <- 3 注意: 二維數組大小的在3到1000范圍內。 二維數組中的每個整數在1到N之間，其中 N 是二維數組的大小。

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

2. 解題

• 參考 數據結構–并查集（Disjoint-Set）

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

本題是684題的升級版本

• 先找有沒有入度為2的節點 node
• 然后遍歷邊的時候先跳過指向 node 的邊
• 最后再遍歷指向 node 的邊

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)//循環+路徑壓縮{int origin = a;while(a != f[a])a = f[a];return f[origin] = a;//路徑壓縮} }; class Solution { public:vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {int N = edges.size();vector<int> indegree(N+1, 0);int node = -1;for(auto e : edges){indegree[e[1]]++;if(indegree[e[1]] > 1)node = e[1];}dsu u(N);int x, y;vector<vector<int>> E;for(auto e : edges){if(node == e[1])//邊指向node，先跳過{E.push_back(e);continue;}if(u.find(e[0]) != u.find(e[1]))//兩個沒有連接u.merge(e[0], e[1]);//把邊連接起來else//已經連接了,有環x = e[0], y = e[1];//記錄下來}for(auto e : E){if(u.find(e[0]) != u.find(e[1]))//兩個沒有連接u.merge(e[0], e[1]);//把邊連接起來else//已經連接了,有環x = e[0], y = e[1];//記錄下來}return {x, y};} };

20 ms 9.9 MB

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。