0%

leetcode 684+547+685

力扣684+685+547题,并查集和拓扑排序的用法

有向图中判断是否有环用拓扑排序,无向图中用并查集。

冗余连接

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
/*
* @lc app=leetcode.cn id=684 lang=java
*
* [684] 冗余连接
*/

// @lc code=start
//方法一:dfs,深度遍历图,查看u是否可以连接到v,如果可以,则他是重复边
//方法二:并查集
class Solution {
//找到根结点
private int find(int []parent, int x){
int node = x;
while(parent[node] != node){
node = parent[node];
}
/*压缩路径:
将根结点相同的点的父节点全部置为根结点
int cur = x;
while(cur != node){
int next = parent[cur];
parent[cur] = node;
node = next;
}
*/
return node;
}

//合并
private boolean union(int []parent, int x, int y){
int parentX = find(parent, x);
int parnetY = find(parent, y);
if(parentX == parnetY){
return false;
}
parent[parentX] = parnetY;
return true;
}

public int[] findRedundantConnection(int[][] edges) {
if(edges == null || edges.length == 0 || edges[0].length == 0){
return new int[0];
}
int len = edges.length;
int[] parent = new int[len];
//parent数组初值
for (int i = 0; i < parent.length; i++) {
parent[i] = i;
}
//遍历每个节点
for(int i = 0; i < len; i++){
if(!union(parent, edges[i][0]-1, edges[i][1]-1)){
return new int[]{edges[i][0], edges[i][1]};
}else{
continue;
}
}
return new int[0];
}
}
// @lc code=end

冗余连接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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/*
* @lc app=leetcode.cn id=685 lang=java
*
* [685] 冗余连接 II
*/

// @lc code=start
//拓扑排序+并查集
/*有根树:唯一入度为0的根结点、其余节点入度全是1、无入度为2的节点。
两种情况:1:不能有入度为2的节点。2:全是入度为1的节点的情况下,不能构成回路
**/
class Solution {

private class UnionFind{
private int[] parent;
public UnionFind(int n){
parent = new int [n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int find(int x){
while(x != parent[x]){
//路径压缩,隔代压缩
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
public boolean union(int x, int y){
int rootx = find(x);
int rooty = find(y);
if(rootx == rooty){
return false;
}
parent[rootx] = rooty;
return true;
}
}
//将removeEdgeIndex去掉以后,剩下的有向边是否构成环
public boolean judgeCircle(int[][] edges, int len, int removeEdgeIndex){
UnionFind unionFind = new UnionFind(len + 1);
for (int i = 0; i < len; i++) {
if(i == removeEdgeIndex){
continue;
}
if(!unionFind.union(edges[i][0], edges[i][1])){
//可以失败,表示两边在一个连同分量,有环
return true;
}
}
return false;
}

public int[] findRedundantDirectedConnection(int[][] edges) {
int len = edges.length;
//第一步,入度数组,记录指向某个节点的边数
int[] inDegree = new int[len + 1];
for(int[] edge : edges){
inDegree[edge[1]]++;
}
//第二步,试着删除入度为2的边
for(int i = len -1; i >= 0; i--){
if(inDegree[edges[i][1]]==2){
//若不构成环,这条边就是要删除的
if(!judgeCircle(edges, len, i)){
return edges[i];
}
}
}
//第三步,试着删除入度为1的边
for(int i = len -1; i >= 0; i--){
if(inDegree[edges[i][1]]==1){
if(!judgeCircle(edges, len, i)){
return edges[i];
}
}
}
throw new IllegalArgumentException("输入不合要求");
}
}
// @lc code=end

朋友圈

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
import java.util.Arrays;

/*
* @lc app=leetcode.cn id=547 lang=java
*
* [547] 朋友圈
*/

// @lc code=start
class Solution {

int find (int[] parent, int x){
if(parent[x] == -1){
return x;
}
return find(parent, parent[x]);
}
void unoin (int[] parent, int x, int y) {
int parentX = find(parent, x);
int parentY = find(parent, y);
//若两个点不在同一个集合,则合并。
if(parentX != parentY){
parent[parentX] = parentY;
}
}

public int findCircleNum(int[][] M) {
int[] parent = new int [M.length];
Arrays.fill(parent, -1);
for (int i = 0; i < M.length; i++) {
for (int j = 0; j < M.length; j++) {
if(M[i][j] == 1 && i != j){
unoin(parent, i, j);
}
}
}
int count = 0;
for (int i = 0; i < parent.length; i++) {
if(parent[i] == -1){
count++;
}
}
return count;
}
}
// @lc code=end
-------------本文结束感谢您的阅读-------------