108.多余的边
题目描述
有一个图，它是一棵树，他是拥有 n 个节点（节点编号1到n）和 n - 1 条边的连通无环无向图，例如如图：
现在在这棵树上的基础上，添加一条边（依然是n个节点，但有n条边），使这个图变成了有环图，如图：
先请你找出冗余边，删除后，使该图可以重新变成一棵树。
输入描述
第一行包含一个整数 N，表示图的节点个数和边的个数。
后续 N 行，每行包含两个整数 s 和 t，表示图中 s 和 t 之间有一条边。
输出描述
输出一条可以删除的边。如果有多个答案，请删除标准输入中最后出现的那条边。
输入示例
3
1 2
2 3
1 3
输出示例
1 3
提示信息
图中的 1 2，2 3，1 3 等三条边在删除后都能使原图变为一棵合法的树。但是 1 3 由于是标准输出里最后出现的那条边，所以输出结果为 1 3
数据范围：
1 <= N <= 1000.
解题思路
import java.util.*;
class Main {
static class DisJoint {
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 n) {
return father[n] == n ? n : (father[n] = find(father[n]));
}
public void join(int a, int b) {
a = find(a);
b = find(b);
if (a == b) {
return;
}
father[b] = a;
}
public boolean isSame(int a, int b) {
a = find(a);
b = find(b);
return a == b;
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] ans = new int[2];
DisJoint disJoint = new DisJoint(n);
for (int i = 0; i < n; i++) {
int a = in.nextInt(), b = in.nextInt();
if (disJoint.isSame(a, b)) {
ans[0] = a;
ans[1] = b;
}
disJoint.join(a, b);
}
in.close();
System.out.println(ans[0] + " " + ans[1]);
}
}
109.多余的边II
题目描述
有一种有向树,该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。有向树拥有 n 个节点和 n - 1 条边。如图：
现在有一个有向图，有向图是在有向树中的两个没有直接链接的节点中间添加一条有向边。如图：
输入一个有向图，该图由一个有着 n 个节点(节点编号 从 1 到 n)，n 条边，请返回一条可以删除的边，使得删除该条边之后该有向图可以被当作一颗有向树。
输入描述
第一行输入一个整数 N，表示有向图中节点和边的个数。
后续 N 行，每行输入两个整数 s 和 t，代表这是 s 节点连接并指向 t 节点的单向边
输出描述
输出一条可以删除的边，若有多条边可以删除，请输出标准输入中最后出现的一条边。
输入示例
3
1 2
1 3
2 3
输出示例
2 3
提示信息
在删除 2 3 后有向图可以变为一棵合法的有向树，所以输出 2 3
数据范围：
1 <= N <= 1000.
解题思路
代码没有参考卡哥的，我结合采用了chatGpt的答案。同时，对并查集这个类构造时，不用join和isSame两个方法，用一个union方法来执行这两个方法的功能。不成环才加入集合。
不同情况如图
情况一(纯成环):
模拟输入为
3
1 2
2 3
3 1
graph LR
a1([a]) --> b1([b])
b1 --> c1([c])
c1 --> a1
删除最后想加进来的边即可
情况二(有入度为2):
模拟输入
3
1 2
2 3
1 3
graph LR
a2([a]) --> b2([b])
b2 --> c2([c])
a2 --> c2
删除后加进来的冲突边
情况三(既成环又有入度为2):
模拟输入为
1 2
2 3
3 1
4 1
graph LR
a3([a]) --> b3([b])
b3 --> c3([c])
c3 --> a3
d4([d]) --> a3
此时cand1={3,1}和cand2={4,1}。在构建并查集时，会忽略cand2，那么就将情况转变为了类似情况一的情况。只不过不同的是情况一没有入度为2的节点。也就是说它的cand1==null
import java.util.*;
public class Main {
static class DSU {
int[] father;
DSU(int n) {
father = new int[n + 1];
for (int i = 1; i <= n; i++) {
father[i] = i;
}
}
int find(int x) {
if (father[x] != x) father[x] = find(father[x]);
return father[x];
}
boolean union(int a, int b) {
int ra = find(a), rb = find(b);
// 成环
if (ra == rb) return false;
father[rb] = ra;
return true;
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[][] edges = new int[n][2];
for (int i = 0; i < n; i++) {
edges[i][0] = in.nextInt();
edges[i][1] = in.nextInt();
}
int[] parent = new int[n + 1];
Arrays.fill(parent, 0);
// 入度为 2 的两条边
int[] cand1 = null;
int[] cand2 = null;
// 1. 找入度为 2
for (int i = 0; i < n; i++) {
int u = edges[i][0];
int v = edges[i][1];
if (parent[v] == 0) {
parent[v] = u;
} else {
cand1 = new int[]{parent[v], v};
cand2 = new int[]{u, v};
break;
}
}
// 2. 并查集，必要时跳过 cand2
DSU dsu = new DSU(n);
for (int i = 0; i < n; i++) {
int u = edges[i][0];
int v = edges[i][1];
if (cand2 != null && u == cand2[0] && v == cand2[1]) {
continue; // 跳过 cand2
}
if (!dsu.union(u, v)) {
// 成环
if (cand1 == null) {
// 情况 1：纯成环
System.out.println(u + " " + v);
return;
} else {
// 情况 3：入度 2 + 成环
// 多余的一定是第一次出现的。
System.out.println(cand1[0] + " " + cand1[1]);
return;
}
}
}
// 3. 情况 2：只有入度 2
System.out.println(cand2[0] + " " + cand2[1]);
}
}
评论