Day56–图论–108. 冗余的边（卡码网），109. 冗余的边II（卡码网）
今天又是练习并查集的一天。第一题很简单，第二题有多种情况，如果不熟悉图的话，基本上是想不出来的。建议思考超过10分钟，直接看题解。跟着题解抄一遍，然后再自己写一遍思路，比愣头青去想好，效率更高。
108. 冗余的边（卡码网）
方法：并查集
思路：
使用并查集，将每个边的from to都加到集合里面。
如果发现from to已经在集合里了，就说明他们在同一颗树上。
如果再把他们连起来，就会成环。所以这是要删除的边
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
Disjoint dj = new Disjoint(n);
while (n-- > 0) {
int from = in.nextInt();
int to = in.nextInt();
// 如果发现from to已经在集合里了，就说明他们在同一颗树上
// 如果再把他们连起来，就会变成图。所以这是要删除的边
if (dj.isSame(from, to)) {
System.out.println(from + " " + to);
return;
} else {
// 每个from to都加到集合里面
dj.join(from, to);
}
}
}
}
class Disjoint {
private int[] father;
public Disjoint(int n) {
father = new int[n + 1];
for (int i = 0; i <= n; i++) {
father[i] = i;
}
}
public int find(int a) {
if (a == father[a]) {
return a;
} else {
return father[a] = find(father[a]);
}
}
public boolean isSame(int o1, int o2) {
return find(o1) == find(o2);
}
public void join(int o1, int o2) {
int root1 = find(o1);
int root2 = find(o2);
if (root1 == root2) {
return;
}
father[o2] = o1;
}
}
109. 冗余的边II（卡码网）
方法：并查集
思路：
两个方向
- 图中有一个入度为2的点
- 情况一：如果我们找到入度为2的点，那么删一条指向该节点的边就行了。
- 情况二，入度为2的点，只能删特定的一条边，因为有可能一删就不成树了，有孤点。
- 综上，鉴于情况二，我们要模拟删除，看看它删后是否还构成树；鉴于情况一，如果都能删，题目要求要优先删除后面的。
- 实际代码怎么做？
- 倒序遍历入度为2的边，模拟删除后，是否还能构成树，能的话删。不能的话，删第二条边。
- 图中有一个有向环
- 删掉构成环的边就行了（和上题差不多）
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[][] edges = new int[n][2];
int[] inDegree = new int[n + 1];
for (int i = 0; i < n; i++) {
int from = in.nextInt();
int to = in.nextInt();
// 节点to的入度加一
inDegree[to]++;
edges[i][0] = from;
edges[i][1] = to;
}
// 检查edges中是否有入度为2的节点
List<Integer> twoInDegree = new ArrayList<>();
// 因为要满足情况一，优先输出后加入的边，需要倒序遍历
for (int i = n - 1; i >= 0; i--) {
if (inDegree[edges[i][1]] == 2) {
// 这里加的这个i是edges中的索引
twoInDegree.add(i);
}
}
// 索引值
int i;
if (twoInDegree.size() > 0) {
// 这条是最后加入的边
i = twoInDegree.get(0);
// 如果删除后仍能构成树，证明是情况一，直接删这条
if (isTreeAfterRemove(edges, i, new Disjoint(n))) {
} else {
// 如果不能构成树，证明是情况二，删另一条
i = twoInDegree.get(1);
}
} else {
// 如果没有入度为2的边，走到这里，就是情况三：删除构成有向环的边
// 注意，不要传用过的并查集。这里要传一个新的。
i = getRemoveEdge(edges, new Disjoint(n));
}
// 打印输出
System.out.println(edges[i][0] + " " + edges[i][1]);
}
// 模拟删除索引为Index这条边，看看剩下的边是否能构成树
private static boolean isTreeAfterRemove(int[][] edges, int index, Disjoint dj) {
for (int i = 0; i < edges.length; i++) {
// 模拟删除索引为Index这条边，看看剩下的边是否能构成树
if (i == index) {
continue;
}
int from = edges[i][0];
int to = edges[i][1];
// 剩下的from to，还有不在一个图中的，证明存在孤点
if (dj.isSame(from, to)) {
return false;
}
dj.join(from, to);
}
// 模拟删除后，仍然能构成树
return true;
}
// 情况三：删除构成有向环的边。和108冗余的边是一样的操作。
private static int getRemoveEdge(int[][] edges, Disjoint dj) {
int i=0;
for (i = 0; i < edges.length; i++) {
int from = edges[i][0];
int to = edges[i][1];
if (dj.isSame(from, to)) {
break;
} else {
dj.join(from, to);
}
}
return i;
}
}
// 并查集
class Disjoint {
private int[] father;
public Disjoint(int n) {
father = new int[n + 1];
for (int i = 0; i <= n; i++) {
father[i] = i;
}
}
public int find(int a) {
if (a == father[a]) {
return a;
} else {
return father[a] = find(father[a]);
}
}
public boolean isSame(int o1, int o2) {
return find(o1) == find(o2);
}
public void join(int o1, int o2) {
int root1 = find(o1);
int root2 = find(o2);
if (root1 == root2) {
return;
}
father[o2] = o1;
}
}
代码随想录中，给出的Java的版本，写得有点累赘。本篇代码改自卡尔的C++版本题解，自认为写得更加清晰一点。符合卡尔解题的时候用的思路。
勘误：
之前并查集理解得不够透彻，join方法写错了。
原来是：
public void join(int o1, int o2) {
int root1 = find(o1);
int root2 = find(o2);
if (root1 == root2) {
return;
}
father[o2] = o1;
}
现在是：
public void join(int o1, int o2) {
int root1 = find(o1);
int root2 = find(o2);
if (root1 == root2) {
return;
}
father[root2] = root1;
}
为什么必须连接根节点？
假设我们要合并两个节点o1和o2，步骤应该是：
- 先通过
find找到o1的根节点root1，o2的根节点root2。 - 如果
root1 != root2，说明两个节点属于不同集合，需要合并。 - 合并的是两个集合的根节点（即
root2的父节点指向root1），而不是直接让o2的父节点指向o1。
举例：
假设现在有两个独立的集合：
- 集合 1：
1是根节点（father[1] = 1），2的父节点是1（father[2] = 1）。 - 集合 2：
3是根节点（father[3] = 3），4的父节点是3（father[4] = 3）。
现在要合并2和4（即o1=2，o2=4）：
- 先找根节点：
root1 = find(2) = 1，root2 = find(4) = 3。 - 正确的合并：
father[root2] = root1（即father[3] = 1）。
合并后，两个集合的根节点都是1，整个集合结构为：1是根，2和3的父节点是1，4的父节点是3。
如果错误地写成father[o2] = o1（即father[4] = 2）：
- 此时
4的父节点是2，但2的父节点是1，3的父节点还是3（仍然是独立根节点）。 - 这会导致
3和4被错误地分割在不同集合中（find(3) = 3，find(4) = 1），但实际上4原本属于3的集合，合并后应该同属一个集合。