第11章图论-part06，继续并查集，今天是应用题，要将题意转化为并查类问题。
108. 冗余连接
1.1 解题分析
题目说是无向图，返回一条可以删去的边，使得结果图是一个有着N个节点的树（一个根节点）。如果有多个答案，则返回二维数组中最后出现的边。
解题思路：从前往后遍历每一条边，优先让前面的边先连上，如果边的两个节点不在同一个集合，就加入集合（即同一个根节点）；如果边上的两个节点已经在同一个集合，那么再加一条边就会成环，此时找到答案。
1.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
| import java.util.Scanner;
public class Main {
static int[] father;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
father = new int[n + 1];
for (int i = 0; i <= n; i++) {
father[i] = i;
}
while (n-- > 0) {
int u = scanner.nextInt();
int v = scanner.nextInt();
int fu = find(u);
int fv = find(v);
if (fu == fv) {
System.out.println(u + " " + v);
break;
}
father[fu] = fv;
}
}
private static int find(int u) {
if (u == father[u]) return u;
else {
father[u] = find(father[u]);
return father[u];
}
}
}
|
109. 冗余连接II
2.1 解题分析
正确的突破点是：有向图有一个节点的入度必定为2（情况1、2）；或者情况3，n个节点依次连接成环，此时可以用并查集来删除边，和上一题一样。
情况1：删除任意一条边，都可以变成有向树；
情况2：只能删除特定边，删除另一条边后不符合一个有向树的定义。
2.2 解题小结
这道题代码比较难写，有空要再做一遍，主要是在Main类下定义静态内部类Edge、Disjoint之后会方便很多。作为工具类，Edge用于保存每条边，Disjoint构建并查集的模板，用于判断连通性。
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
| import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
public class Main {
static class Disjoint {
private final int[] father;
public Disjoint(int n) {
father = new int[n];
for (int i = 0; i < n; i++) {
father[i] = i;
}
}
public int find(int u) {
if (u == father[u]) return u;
return father[u] = find(father[u]);
}
public void join(int u, int v) {
u = find(u);
v = find(v);
if (u == v) return;
father[u] = v;
}
public boolean isSame(int u, int v) {
return find(u) == find(v);
}
}
static class Edge {
int s;
int t;
public Edge(int s, int t) {
this.s = s;
this.t = t;
}
}
static class Node {
int id;
int in;
int out;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
List<Edge> edges = new ArrayList<>();
Node[] nodeMap = new Node[n + 1];
for (int i = 1; i <= n; i++) {
nodeMap[i] = new Node();
}
Integer doubleIn = null;
for (int i = 0; i < n; i++) {
int s = scanner.nextInt();
int t = scanner.nextInt();
nodeMap[t].in++;
if (nodeMap[t].in == 2) doubleIn = t;
Edge edge = new Edge(s, t);
edges.add(edge);
}
Edge result = null;
if (doubleIn != null) {
List<Edge> doubleInEdges = new ArrayList<>();
for (Edge edge : edges) {
if (edge.t == doubleIn) doubleInEdges.add(edge);
if (doubleInEdges.size() == 2) break;
}
Edge edge = doubleInEdges.get(1);
if (isTreeAfterDelete(edges, edge, nodeMap)) {
result = edge;
} else {
result = doubleInEdges.get(0);
}
} else {
result = getRemoveEdge(edges, nodeMap);
}
System.out.println(result.s + " " + result.t);
}
private static Edge getRemoveEdge(List<Edge> edges, Node[] nodeMap) {
Disjoint disjoint = new Disjoint(nodeMap.length + 1);
for (Edge e : edges) {
if (disjoint.isSame(e.s, e.t)) return e;
disjoint.join(e.s, e.t);
}
return null;
}
private static boolean isTreeAfterDelete(List<Edge> edges, Edge deleteEdge, Node[] nodeMap) {
Disjoint disjoint = new Disjoint(nodeMap.length + 1);
for (Edge e : edges) {
if (e == deleteEdge) continue;
if (disjoint.isSame(e.s, e.t)) return false;
disjoint.join(e.s, e.t);
}
return true;
}
}
|
3. 今日收获