leetcode684. Redundant Connection

Posted on |

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
4
5
 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:

1
2
3
4
5
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.

Update (2017-09-26):
We have overhauled the problem description + test cases and specified clearly the graph is an undirected graph. For the directed graph follow up please see Redundant Connection II). We apologize for any inconvenience caused.

思路

并查集的思想

union: 把分别含有u,v的集合Merge到一起，如果u,v已经在一个集合 返回false
如果不在一个集合 就把一个集合merge到另一个集合中 （把rank小的merge到rank大的集合）

find:返回它的祖先节点(cluster id） 每个节点都有它的parent 在找祖先节点的过程额外地Path compression 回溯的过程中把其Parent也指向祖先节点（如果开始指向的不是祖先节点的话）

这样会降低后几次查找的时间复杂度

可能第一次找是o(n)(链表长度) 第二次找o（1）

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
class unionset{
public:
    vector<int> parent;
    vector<int> rank;
	
    unionset(int n){
    parent=vector<int>(n+1,0);
    rank=vector<int>(n+1,0);
        for(int i=1;i<=n;i++)
	parent[i]=i;
	}
	
	bool Union(int u1,int u2){
		int p1=find(u1);
		int p2=find(u2);
		if(p1==p2) return false;
		if(rank[p1]>rank[p2]){
			parent[p2]=p1;
		}
        else if(rank[p2]>rank[p1]){
            parent[p1]=p2;
        }
        else {
            parent[p1]=p2;
            rank[p2]++;
        }
        return true;
		
	}
    int find(int num){
        if(num!=parent[num]){
            parent[num]=find(parent[num]);//find(num)一直自己调用自己 错的 find(parent[num]) 往上回溯
        }
        return parent[num];
    }
	
};

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n=edges.size();
        unionset u(n);
         vector<int> v;
        for(vector<vector<int>>::iterator it=edges.begin();it!=edges.end();it++){
            cout<<(*it)[0]<<" "<<(*it)[1]<<endl;
           if(!u.Union((*it)[0],(*it)[1])){
               cout<<1<<endl;
               v.push_back((*it)[0]);
               v.push_back((*it)[1]);
                   break;
           } 
            
        }
        return v;
    }
};