LeetCode 题解——Redundant Connection II

发表于 | 分类于 | 阅读次数:
字数统计: 580 字

LeetCode 题解——Redundant Connection II

题意

给出一个有向图，求其有向的最小生成树（除了根节点之外所有的节点都有一条入边指向它），同时给出的有向图刚好只多出一条边

题解

前一道题是求只多出一条边的无向图的最小生成树，使用并查集很容易就能够求解。

这一道有向图的题就比较复杂一点了，有向图的最小生成树又叫最小树形图，常规算法是使用朱刘算法。这里因为只多出一条边，所以不用这么麻烦。

总共有三种情况：

  1. 有环，但是没有入度为2的节点

  1. 有环，同时有入度为2的节点

  1. 无环，有入度为2的节点

第一种情况，按照无向图的处理方式进行就行了，使用并查集返回最后一条形成环的边。

后面两种情况，首先要找到入度为2的节点，选出指向这个节点的两条边，处理完其他的边以后处理这两条边，使用并查集找出最后一个连接的两个节点已经在同一集合中的边

代码

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
class Solution {
public:
    int par[3000];
    
    void init(int n)
    {
        for(int i=1;i<=n;i++)
            par[i] = i;
    }
    
    int find(int x)
    {
        if(par[x] == x) return x;
        else return par[x] = find(par[x]);
    }
    
    void unite(int x, int y)
    {
        x = find(x);
        y = find(y);
        if(x == y) return;
        par[y] = x;
    }
    
    // 并查集
    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        int len = edges.size();
        init(len);
        vector<int> indegre(len, 0), outdegre(len, 0);
        vector<vector<int> > problem_edge;
        int node = 0;
        // 统计入度，找到入度为2的点
        for(auto i:edges)
        {
            indegre[i[1]]++;
            if(indegre[i[1]] == 2) node = i[1];
        }
        int flag=0;
        for(auto i:edges)
        {
            if(i[1] == node)
            {
                problem_edge.push_back(i);
                continue;
            }
            // 有环的情况
            int a = find(i[0]), b= find(i[1]);
            if(a == b) 
                return i;
            unite(i[0], i[1]);
        }
        // 无环的情况，从入度为2的节点入手
        for(auto i:problem_edge)
        {
            int a = find(i[0]), b= find(i[1]);
            if(a == b) return i;
            else unite(a,b);
        }
    }
};

更多LeetCode题解，欢迎查看我的GitHub项目