1怯屉、題目鏈接
https://leetcode.com/problems/redundant-connection/
2梧兼、解題思路
這道題的意思是說白翻，給你一個(gè)二維數(shù)組瓷式，這個(gè)二維數(shù)組代表一個(gè)圖欣福，這個(gè)圖由一顆有著N個(gè)節(jié)點(diǎn)的樹再加一條附加邊構(gòu)成责球，[[a1, b1], [a2, b2], [a3, b3]]，也就是說二維數(shù)組里面的每一項(xiàng)都是圖的一條邊拓劝，讓你返回某一條邊雏逾，當(dāng)這條邊刪除之后使得剩下的節(jié)點(diǎn)是一棵樹，如果有多個(gè)答案的話郑临，就返回最后一個(gè)栖博；換句話說，這個(gè)圖中有一個(gè)閉環(huán)厢洞，然后讓你找出一條可以刪除的邊仇让，使其成為一棵樹，這樣的話我們就可以來分析一下躺翻，怎么知道他是一個(gè)閉環(huán)呢丧叽？
如上圖所示，我們只需要找到其中一條邊兩個(gè)節(jié)點(diǎn)的頂點(diǎn)（即根結(jié)點(diǎn)）相同即可公你，那么我們怎么保證它是最后一條呢踊淳？因?yàn)轭}目說了只有一條附加邊；所以我們先遍歷整個(gè)二維數(shù)組陕靠，也就是圖的邊迂尝，然后每次都把邊的兩個(gè)頂點(diǎn)找出來脱茉，通過一個(gè)數(shù)組來記錄，假設(shè) nums[a] = b垄开，那么就有a的頂點(diǎn)是b琴许，通過這種數(shù)據(jù)存儲的方式我們最終可以遞歸算出某條邊兩個(gè)節(jié)點(diǎn)的頂點(diǎn)，如果這兩個(gè)節(jié)點(diǎn)的頂點(diǎn)相同溉躲，那么我們就返回這條邊虚吟，這條邊就是附加邊，如果頂點(diǎn)不相同签财，那么我們將較小節(jié)點(diǎn)的根結(jié)點(diǎn)置為較大的那個(gè)節(jié)點(diǎn)。
3偏塞、代碼
- Java
public int[] findRedundantConnection(int[][] edges) {
int[] nums = new int[1001];
for (int i = 0; i < edges.length; i++) {
int root1 = findRoot(edges[i][0], nums); //通過遞歸找第一個(gè)節(jié)點(diǎn)的根結(jié)點(diǎn)
int root2 = findRoot(edges[i][1], nums); //通過遞歸找第二個(gè)節(jié)點(diǎn)的根結(jié)點(diǎn)
if (root1 == root2) { //如果兩個(gè)節(jié)點(diǎn)的根結(jié)點(diǎn)相同唱蒸，那么說明有環(huán)
return edges[i];
} else {
nums[root1] = root2; //如果兩個(gè)根結(jié)點(diǎn)不相同，那么將第一個(gè)節(jié)點(diǎn)的根結(jié)點(diǎn)置為第二個(gè)節(jié)點(diǎn)
}
}
return new int[]{0, 1};
}
public int findRoot(int x, int[] nums) {
if (nums[x] == 0) return x;
x = nums[x];
return findRoot(x,nums);
}
