LeetCode684-多余的边：递归除边+并查集C++解法

题目描述：

给定一棵n各节点(节点值1~n)的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。

请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的边。

原题参考链接：https://leetcode-cn.com/problems/7LpjUW

分析：

简而言之，本题默认给出的是包含一个单独闭环的图，只需要按照输入edges的逆序定位到首次出现在闭环上的边，即可将图还原为树。

示例1：

1 输入: edges = [[1,2],[1,3],[2,3]]
2 输出: [2,3]

示例2：

1 输入: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
2 输出: [1,4]

Cpp解法1-递归除边：

search_one_pair 函数配合 vectoredgeVisited 来寻找未被访问的路径与其节点；Cut_pair函数根据unordered_mapM来对每个节点的Edge计数，对M[Node]==1的Node调用search_one_pair查找配对Node_target，此过程更新M；再对M[Node_target]递归使用Cut_pair方法；去除的是非环边：

 1 class Solution {
 2 private:
 3 vector<bool>edgeVisited;
 4 unordered_map<int,int>M;
 5 int search_one_pair(vectorint>>& edges,int key){
 6     for(int i=0;i){
 7         if(edgeVisited[i]==true)continue;
 8         if(edges[i][0]==key){
 9             edgeVisited[i]=true;
10             return edges[i][1];
11         }
12         if(edges[i][1]==key){
13             edgeVisited[i]=true;
14             return edges[i][0];
15         }
16     }
17     return -1;
18 }
19 void Cut_pair(vectorint>>& edges){
20     auto q=M.begin();
21         while(q!=M.end()){
22             if(q->second==1){
23                 q->second=0;
24                 int temp=search_one_pair(edges,q->first);
25                 M[temp]--;
26                 //cout<first<<"*"<second<<" ";
27                 if(M[temp])Cut_pair(edges);//Cut again or not
28             }
29             q++;
30         }
31      return;
32 }
33 public:
34     vector<int> findRedundantConnection(vectorint>>& edges) {
35         edgeVisited.resize(edges.size(),false);
36         for(int i=0;i){
37             M[edges[i][0]]++;
38             M[edges[i][1]]++;
39         }
40         Cut_pair(edges);
41         for(int i=edges.size()-1;i>=0;i--){
42             if(M[edges[i][0]]>0 && M[edges[i][1]]>0){
43                 //cout<<"^"<
44                 return edges[i];
45             }
46         }
47         return {};
48     }
49 };

时间复杂度：O(n^2)

空间复杂度：O(n)

注意：

unordered_map相较于其他存储结构有利于降低时间复杂度，否则会达到时间复杂度上限。

Cpp解法2-并查集：

分析：

对于任何一棵有n个节点的树只可能有n-1条边，任何闭环上的边均同时属于其两个节点所在的子图，利用此条件可以快速按照egde顺序来合并各子树，最后返回的边就是最后出现在edge中的闭环边；

注意：初始化节点为单独子树，初始vectorFatherIndex长度为节点个数n=egdes.size()-1。

对示例1：

 1 class Solution {
 2 private:
 3 int findFatherNode(vector<int>& FatherIndex,int point){
 4     if(FatherIndex[point]==point)return point;
 5     FatherIndex[point]=findFatherNode(FatherIndex,FatherIndex[point]);
 6     return FatherIndex[point];
 7 }
 8 public:
 9     vector<int> findRedundantConnection(vectorint>>& edges) {
10         vector<int>FatherIndex(edges.size()+1);
11         for(int i=1;i){
12             FatherIndex[i]=i;//initialize n subtrees
13         }
14         for(int i=0;i){
15             int Fres1=findFatherNode(FatherIndex,edges[i][0]);
16             int Fres2=findFatherNode(FatherIndex,edges[i][1]);
17             if(Fres1==Fres2){
18                 return edges[i];//last edge
19             }else{
20                 FatherIndex[Fres2]=Fres1;
21             }
22         }
23         return {};
24     }
25 };

时间复杂度：O(n)

空间复杂度：O(n)