Lintcode 1088. Redundant Connection

Description

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.

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.

Have you met this question in a real interview?  

Example

Example 1:

Input:  [[1,2], [1,3], [2,3]]
Output:  [2,3]	
Explanation: 
  looks like:
	  1
	 / \
	2 - 3

Example 2:

Input:  [[1,2], [2,3], [3,4], [1,4], [1,5]]
Output:  [1,4]	
Explanation:
	looks like:
	5 - 1 - 2
	    |   |
	    4 - 3

Code (Java):

 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71

public class Solution {     /**      * @param edges: List[List[int]]      * @return: List[int]      */     public int[] findRedundantConnection(int[][] edges) {         // write your code here         int[] res = new int[2];                   if (edges == null || edges.length == 0) {             return res;         }                   UF uf = new UF(edges.length + 1);                   for (int[] edge : edges) {             uf.union(edge[0], edge[1]);         }                   return uf.getAns();     } }   class UF {     private int[] parents;     private int n;           private int[] ans;           public UF(int n) {         this.n = n;         parents = new int[n];         ans = new int[2];                   for (int i = 0; i < n; i++) {             parents[i] = i;         }     }           public void union(int a, int b) {         int pa = find(a);         int pb = find(b);                   if (pa != pb) {             parents[pa] = pb;         } else {             ans[0] = a;             ans[1] = b;         }     }           public int find(int a) {         int root = a;         while (parents[root] != root) {             root = parents[root];         }                   // path compression         while (root != a) {             int parent = parents[a];             parents[a] = root;             a = parent;         }                   return root;     }           public int[] getAns() {         return ans;     } }