代码随想录训练营第五十六天| 108.冗余连接 109.冗余连接II
108.冗余连接
题目链接：卡码网题目链接（ACM模式） (opens new window)
讲解链接：代码随想录
并查集可以解决什么问题：两个节点是否在一个集合，也可以将两个节点添加到一个集合中。
引自代码随想录：
题目说是无向图，返回一条可以删去的边，使得结果图是一个有着N个节点的树（即：只有一个根节点）。
如果有多个答案，则返回二维数组中最后出现的边。
那么我们就可以从前向后遍历每一条边（因为优先让前面的边连上），边的两个节点如果不在同一个集合，就加入集合（即：同一个根节点）。
如图所示，节点A 和节点 B 不在同一个集合，那么就可以将两个 节点连在一起。
如果边的两个节点已经出现在同一个集合里，说明着边的两个节点已经连在一起了，再加入这条边一定就出现环了。
如图所示：
已经判断 节点A 和 节点B 在在同一个集合（同一个根），如果将 节点A 和 节点B 连在一起就一定会出现环。
java：
import java.util.Scanner;
public class Carlcode108 {
//并查集模版
static class DisJoint{
private int[] father;
//初始化
public DisJoint(int n){
father = new int[n];
for (int i = 0; i < n; i++) {
father[i] = i;
}
}
//查询
public int find(int n){
return n == father[n] ? n : (father[n] = find(father[n]));
//如果当前节点父节点是自己 就直接输出自己
//否则就一直递归查找当前节点的父节点 直到根节点为止
//路径压缩（递归）
}
//合并
public void join(int n,int m){
m = find(m);
n = find(n);
if(n == m) return;//如果根节点相同则说明在同一个集合里
father[m] = n;//否则就把m父节点指向n的父节点
}
public boolean isSame(int n,int m){
n = find(n);
m = find(m);
//isSame用于判断节点n m 是否属于同一个集合
return n == m;//让他们根节点直接相同
}
}
public static void main(String[] args) {
int n;
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
DisJoint disJoint = new DisJoint(n + 1);
int start, end;
for (int i = 0; i < n; i++) {
start = scanner.nextInt();
end = scanner.nextInt();
if(disJoint.isSame(start,end)){
System.out.println(start + " " + end);
//如果集合中start和end两个点所指向的根节点都是一个节点
//说明已经出现过start和end 的根节点了 直接输出
}else{
disJoint.join(start,end);
}
}
}
}
109.冗余连接II
题目链接：卡码网题目链接（ACM模式） (opens new window)
讲解链接：代码随想录
这道题变成了有向树+一条有向边
若有多条边可以删除，请输出标准输入中最后出现的一条边 要删除次序比较后的那条边
有向树的性质，如果是有向树的话，只有根节点入度为0，其他节点入度都为1（因为该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点）。
有三种情况
第一种 如果我们找到入度为2的点，那么删一条指向该节点的边就行了。
可以删除1->3 2->3 都可以构成有向树
第二种 只能删特定的一条边，如图：
入度为2的节点为3 只能删除1->3（该情况下 4为根节点） 如果删除4->3就没有根节点 无法链接所有的点
综上，如果发现入度为2的节点，我们需要判断 删除哪一条边，删除后本图能成为有向树。如果是删哪个都可以，优先删顺序靠后的边。
情况三 有环出现 只需要删除环里的任意产生环的一条边即可
1->3（3为根节点）3->2（2为根节点）2->1（1为根节点）
java:
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Carlcode109 {
public static class DisJoint{
private int[] father;
public DisJoint(int n){
father = new int[n];
for (int i = 0; i < n; i++) {
father[i] = i;
}
}
//查询
public int find(int n){
return n == father[n] ? n : (father[n] = find(father[n]));
}
//合并
public void join(int n,int m){
n = find(n);
m = find(m);
if(m == n) return;
father[m] = n;
}
//判断相同
public boolean isSame(int n, int m){
return find(n) == find(m);
}
}
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 ans = null;
//存在入度为2的节点 即要消除入度为2的问题 同时解决可能存在的环
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(isTreeWithExclude(edges,edge,nodeMap)){
ans = edge;
} else{
//不存在入度为2的节点 则只需要解除环即可
}
}
System.out.println(ans.s + " " + ans.t);
}
public static boolean isTreeWithExclude(List<Edge> edges, Edge exculdEdge,Node[] nodeMap){
DisJoint disJoint = new DisJoint(nodeMap.length + 1);
for(Edge edge : edges){
if(edge == exculdEdge) continue;//成环 不是树
if(disJoint.isSame(edge.s, edge.t)){
return false;
}
disJoint.join(edge.s,edge.t);
}
return true;
}
public static Edge getRemoveEdge(List<Edge> edges, Node[] nodeMap){
int length = nodeMap.length;
DisJoint disJoint = new DisJoint(length);
for(Edge edge : edges){
if(disJoint.isSame(edge.s, edge.t)) return edge;
disJoint.join(edge.s,edge.t);
}
return null;
}
}