資訊專欄INFORMATION COLUMN
Problem
In this problem, a tree is an undirected graph that is connected and has no cycles.
The given input is a graph that started as a tree with N nodes (with distinct values 1, 2, ..., N), with one additional edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.
The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] with u < v, that represents an undirected edge connecting nodes u and v.
Return an edge that can be removed so that the resulting graph is a tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array. The answer edge [u, v] should be in the same format, with u < v.
Example 1:
Input: [[1,2], [1,3], [2,3]] Output: [2,3] Explanation: The given undirected graph will be like this: 1 / 2 - 3
Example 2:
Input: [[1,2], [2,3], [3,4], [1,4], [1,5]]
Output: [1,4]
Explanation: The given undirected graph will be like this:
5 - 1 - 2
| |
4 - 3
Note:
The size of the input 2D-array will be between 3 and 1000.
Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.
class Solution {
public int[] findRedundantConnection(int[][] edges) {
UnionFind uf = new UnionFind(edges.length+1);
for (int[] edge: edges) {
int a = edge[0], b = edge[1];
if (uf.find(a) == uf.find(b)) return edge;
else uf.union(a, b);
}
return new int[0];
}
}
class UnionFind {
int[] parents;
public UnionFind(int n) {
parents = new int[n];
for (int i = 0; i < n; i++) parents[i] = i;
}
public int find(int a) {
if (parents[a] != a) return find(parents[a]);
else return a;
}
public void union(int a, int b) {
int pA = find(a), pB = find(b);
if (pA != pB) parents[pB] = pA;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/72549.html
摘要：標(biāo)題文字簡(jiǎn)化風(fēng)格的絕對(duì)路徑。我們可以首先將所有的內(nèi)容從中分離出來(lái)，然后分別處理。這里我們需要用到堆棧的數(shù)據(jù)結(jié)構(gòu)。堆棧有很多種實(shí)現(xiàn)方式，中的類類都可以實(shí)現(xiàn)其功能。我們將讀到的路徑入棧，根據(jù)操作符出棧，最后將棧中剩余的元素組織成路徑返回即可。 標(biāo)題文字 Given an absolute path for a file (Unix-style), simplify it. For exa...
Problem Given an absolute path for a file (Unix-style), simplify it. For example, path = /home/, => /home path = /a/./b/../../c/, => /c path = /a/../../b/../c//.//, => /c //here: b is cancelle...
摘要：這樣，我們可以保證隊(duì)列里的元素是從頭到尾降序的，由于隊(duì)列里只有窗口內(nèi)的數(shù)，所以他們其實(shí)就是窗口內(nèi)第一大，第二大，第三大的數(shù)。 Sliding Window Maximum Given an array nums, there is a sliding window of size k which is moving from the very left of the array to...
閱讀 1342·2019-08-30 15:55
閱讀 1644·2019-08-26 10:21
閱讀 3436·2019-08-23 18:28
閱讀 3374·2019-08-23 15:38
閱讀 743·2019-08-23 15:24
閱讀 2134·2019-08-23 13:59
閱讀 773·2019-08-23 11:31
閱讀 2869·2019-08-23 10:53
