LeetCode 题解——Redundant Connection II

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项目