第十一章：图论part06
108. 冗余连接
并查集应用类题目，关键是如何把题意转化成并查集问题
文章讲解
思路
并查集可以解决什么问题：两个节点是否在一个集合，也可以将两个节点添加到一个集合中。
-
题意：无向图，返回一条可以删去的边，使得结果图是一个有着N个节点的树（即：只有一个根节点）。如果有多个答案，则返回二维数组中最后出现的边。那么我们就可以从前向后遍历每一条边（因为优先让前面的边连上），边的两个节点如果不在同一个集合，就加入集合（即：同一个根节点）。
image.png 节点A 和节点 B 不在同一个集合，那么就可以将两个 节点连在一起。
-
如果边的两个节点已经出现在同一个集合里，说明着边的两个节点已经连在一起了，再加入这条边一定就出现环了。
image.png
import java.util.*;
public class Main{
static private int n;
static private int[] father = new int[1005];
// 并查集初始化
static public void init(){
for(int i = 0; i <= n; i++){
father[i] = i;
}
}
// 并查集里寻根的过程
static public int find(int u){
if(u == father[u]){
return u;
}else{
father[u] = find(father[u]);
return father[u];
}
}
// 判断 u 和 v 是否找到同一个根
static public boolean isSame(int u, int v){
return find(u) == find(v);
}
// 将 v -> u 这条边加入并查集
static public void join(int u, int v){
int rootU = find(u);
int rootV = find(v);
if(rootU == rootV) return;// 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
father[rootV] = rootU;
}
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
init();// 初始化并查集
int s, t;
for(int i = 0; i < n; i++){
s = sc.nextInt();
t = sc.nextInt();
if(isSame(s, t)){
System.out.println(s + " " + t);
return;
}else{
join(s, t);
}
}
}
}
109. 冗余连接II
上面两道题目是不是感觉做出自信了，感觉并查集不过如此？
来这道题目 给大家适当一些打击， 难度上来了。
文章讲解
思路
本题的本质是 ：有一个有向图，是由一颗有向树 + 一条有向边组成的 （所以此时这个图就不能称之为有向树），现在让我们找到那条边 把这条边删了，让这个图恢复为有向树。
还有“若有多条边可以删除，请输出标准输入中最后出现的一条边”，这说明在两条边都可以删除的情况下，要删顺序靠后的边
有向树的性质，如果是有向树的话，只有根节点入度为0，其他节点入度都为1（因为该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点）。
-
所以情况一：如果我们找到入度为2的点，那么删一条指向该节点的边就行了。image.png
找到了节点3 的入度为2，删 1 -> 3 或者 2 -> 3 。选择删顺序靠后便可。
-
但 入度为2 还有一种情况，情况二，只能删特定的一条边，如图：image.png
节点3 的入度为 2，但在删除边的时候，只能删 这条边（节点1 -> 节点3），如果删这条边（节点4 -> 节点3），那么删后本图也不是有向树了（因为找不到根节点）。
综上，如果发现入度为2的节点，我们需要判断 删除哪一条边，删除后本图能成为有向树。如果是删哪个都可以，优先删顺序靠后的边。
-
情况三： 如果没有入度为2的点，说明 图中有环了（注意是有向环）。image.png
1. 记录每条边并统计节点入度：
int s, t;
List<int[]> edges = new ArrayList<>(); // 用于存储边
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
int[] inDegree = new int[n + 1]; // 记录节点入度
for (int i = 0; i < n; i++) {
s = sc.nextInt();
t = sc.nextInt();
inDegree[t]++;
edges.add(new int[]{s, t});
}
2. 查找入度为 2 的节点所对应的边并倒序遍历：
List<Integer> vec = new ArrayList<>(); // 记录入度为2的边（如果有的话就两条边）
// 找入度为2的节点所对应的边，注意要倒序，因为优先删除最后出现的一条边
for (int i = n - 1; i >= 0; i--) {
if (inDegree[edges.get(i)[1]] == 2) {
vec.add(i);
}
}
if (!vec.isEmpty()) {
// 放在vec里的边已经按照倒叙放的，所以这里就优先删vec.get(0)这条边
if (isTreeAfterRemoveEdge(edges, vec.get(0))) {
System.out.println(edges.get(vec.get(0))[0] + " " + edges.get(vec.get(0))[1]);
} else {
System.out.println(edges.get(vec.get(1))[0] + " " + edges.get(vec.get(1))[1]);
}
return;
}
3. 在有向图里找到删除的那条边，使其变成树：
public static void getRemoveEdge(List<int[]> edges) {
init(); // 初始化并查集
for (int i = 0; i < n; i++) { // 遍历所有的边
if (same(edges.get(i)[0], edges.get(i)[1])) { // 构成有向环了，就是要删除的边
System.out.println(edges.get(i)[0] + " " + edges.get(i)[1]);
return;
} else {
join(edges.get(i)[0], edges.get(i)[1]);
}
}
}
4. 删一条边之后判断是不是树：
public static boolean isTreeAfterRemoveEdge(List<int[]> edges, int deleteEdge) {
init(); // 初始化并查集
for (int i = 0; i < n; i++) {
if (i == deleteEdge) continue;
if (same(edges.get(i)[0], edges.get(i)[1])) { // 构成有向环了，一定不是树
return false;
}
join(edges.get(i)[0], edges.get(i)[1]);
}
return true;
}
5. 完整代码实现：
以下是完整的 Java 代码实现，结合了以上代码片段：
import java.util.*;
public class Main {
static private int n;
static private int[] father = new int[1001];
// 并查集初始化
static public void init() {
for (int i = 1; i <= n; i++) {
father[i] = i;
}
}
// 并查集里寻根的过程
static public int find(int u) {
if (u == father[u]) {
return u;
} else {
father[u] = find(father[u]);
return father[u];
}
}
// 将 v -> u 这条边加入并查集
static public void join(int u, int v) {
int rootU = find(u);
int rootV = find(v);
if (rootU == rootV) return;
father[rootV] = rootU;
}
// 判断 u 和 v 是否找到同一个根
static public boolean same(int u, int v) {
return find(u) == find(v);
}
// 在有向图里找到删除的那条边，使其变成树
public static void getRemoveEdge(List<int[]> edges) {
init(); // 初始化并查集
for (int i = 0; i < n; i++) { // 遍历所有的边
if (same(edges.get(i)[0], edges.get(i)[1])) { // 构成有向环了，就是要删除的边
System.out.println(edges.get(i)[0] + " " + edges.get(i)[1]);
return;
} else {
join(edges.get(i)[0], edges.get(i)[1]);
}
}
}
// 删一条边之后判断是不是树
public static boolean isTreeAfterRemoveEdge(List<int[]> edges, int deleteEdge) {
init(); // 初始化并查集
for (int i = 0; i < n; i++) {
if (i == deleteEdge) continue;
if (same(edges.get(i)[0], edges.get(i)[1])) { // 构成有向环了，一定不是树
return false;
}
join(edges.get(i)[0], edges.get(i)[1]);
}
return true;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
List<int[]> edges = new ArrayList<>(); // 用于存储边
int[] inDegree = new int[n + 1]; // 记录节点入度
int s, t;
for (int i = 0; i < n; i++) {
s = sc.nextInt();
t = sc.nextInt();
inDegree[t]++;
edges.add(new int[]{s, t});
}
List<Integer> vec = new ArrayList<>(); // 记录入度为2的边（如果有的话就两条边）
// 找入度为2的节点所对应的边，注意要倒序，因为优先删除最后出现的一条边
for (int i = n - 1; i >= 0; i--) {
if (inDegree[edges.get(i)[1]] == 2) {
vec.add(i);
}
}
// 情况一、情况二
if (!vec.isEmpty()) {
// 放在vec里的边已经按照倒叙放的，所以这里就优先删vec.get(0)这条边
if (isTreeAfterRemoveEdge(edges, vec.get(0))) {
System.out.println(edges.get(vec.get(0))[0] + " " + edges.get(vec.get(0))[1]);
} else {
System.out.println(edges.get(vec.get(1))[0] + " " + edges.get(vec.get(1))[1]);
}
} else {
// 处理情况三
// 明确没有入度为2的情况，那么一定有有向环，找到构成环的边返回就可以了
getRemoveEdge(edges);
}
}
}
