685. 冗余连接 II--（每日一难phase--day13）

685. 冗余连接 II

在本问题中，有根树指满足以下条件的 有向 图。该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。

输入一个有向图，该图由一个有着 n 个节点（节点值不重复，从 1 到 n）的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间，这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组 edges 。 每个元素是一对 [ui, vi]，用以表示 有向 图中连接顶点 ui 和顶点 vi 的边，其中 ui 是 vi 的一个父节点。

返回一条能删除的边，使得剩下的图是有 n 个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。

示例 1：

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

示例 2：

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

提示：

n == edges.length
3 <= n <= 1000
edges[i].length == 2
1 <= ui, vi <= n

解析：

• n个顶点存在n-1条边就能保证是一颗树，多一条边会造成三种情况
  
  
• 首先需要统计入度，如果有入度为2的点就需要符合前两种情况，只需要删除造成该点入度为2的其中一条边（共两条）
• 到底删除哪一条？需要使用并查集判断，如果剩余的边仍然够不成一棵树，就说明不是该边需要删除，是二者种的另外一条。
• 针对第三种情况，需要找到造成环的那一条边，如果加入一条边之前，该图已经有相同的父节点，那么加入该边一定会造成环，例如图三。（一定要从前往后判断，这样一定是后边的边造成了环，返回该值即可）。
  - 总结：本题并查集的用途，判断两个点是否存在相同父节点，如果存在相同父节点，那么再在两点上加一条边，就会造成以上三种情况发生。

思路来源，图片来源，代码参考：代码随想录题解

代码：

class Solution {
public:
    int fa[1005];
    
    // 初始化
    void init(){
        for(int i=0;i<1005;i++){
            fa[i]=i;
        }
    }

	// 路径压缩，寻找根节点，并让路径上所有点指向根节点
    int find(int v){
        if(v!=fa[v])
            fa[v]=find(fa[v]);
        return fa[v]; 
    }
    
    // 判断两个点对应的根节点是否相同
    // 如果一天边对应的两个根节点相同，再加上该边一定不是树
    bool same(int u,int v){
        return find(u)==find(v);
    }

	// union操作，将u对应子集添加到v上
    void join(int u,int v){
        fa[find(u)]=find(v);
    }

    // 如果除去该边，剩余边能组成一棵树，这条边是多余的，返回true删除idx对应的这条边
    bool isTreeAfterDelete(vector<vector<int>>& edges,int idx){
        init();
        int n = edges.size();
        for(int i=0;i<n;i++){
        	// 不管该边
            if(i==idx) continue;
            // 剩余边不能组成树（返回false，说明不是这条边的原因）
            if(same(edges[i][0],edges[i][1]))
                return false;
            join(edges[i][0],edges[i][1]);
        }
        return true;
    }

    // 判断是那条边造成了环（从小到大遍历，后边的一条边会造成环，也是需要删除的）
    vector<int> getRemoveEdge(vector<vector<int>>& edges){
        init();
        int n=edges.size();
        for(int i=0;i<n;i++){
            if(same(edges[i][0],edges[i][1]))
                return edges[i];
            join(edges[i][0],edges[i][1]);
        }
        return {};
    }

    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        memset(fa,0,sizeof(fa));
        int n= edges.size();
        int degrees[n+1];
        memset(degrees,0,sizeof(degrees));
        // 统计每个点的入度
        for(auto a :edges){
            degrees[a[1]]++;
        }
        vector<int> vct;

        // 找到入度为2的点对应的两条边
        for(int i=n-1;i>=0;i--){
            if(degrees[edges[i][1]]==2)
                vct.push_back(i);
        }
        
        if(vct.size()>0){
            // 判断是否是该边导致入度为2
            if(isTreeAfterDelete(edges,vct[0]))
                return edges[vct[0]];
            else 
                return edges[vct[1]];
            
        }
        
        return getRemoveEdge(edges);
    }
};
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85

并查集补充 ：684. 冗余连接

class Solution {
public:
    int fa[1005];
    void init(){
        for(int i=0;i<1005;i++){
            fa[i]=i;
        }
    }

	// 路径压缩
	// 1不知道父去问2，2不知道父去问3
	// 4是父亲，4告诉3，fa[3]记录，然后给2返回fa[2]知道了，fa[1]=4知道了
	// 回溯赋值。
    int find(int v){
        if(fa[v]!=v)
            fa[v]=find(fa[v]);
        return fa[v];
    }

	// 将u的父节点的父亲（fa[find(u)]）变为v的父亲find(v)
    void un(int u,int v){
        fa[find(u)]=find(v);
    }

	// 如果两者已经连通，那（u，v）这条边就是多余的
	// same判断两点是否连通
    bool same(int u,int v){
        return find(u)==find(v);
    }
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n=edges.size();
        init();
        for(int i=0;i<n;i++){
            int x=edges[i][0],y=edges[i][1];
            if(same(x,y))
                return {x,y};
            un(x,y);
        }
        return {};
    }
};
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