代码随想录算法训练营打卡第56天
前言
今天依旧是并查集的一天，一共有两题，第一道题感觉还可以，第二道题研究了之后直接放弃，感觉还不适合我现在的水平。。。
冗余连接
文章链接：代码随想录
题目链接：108. 冗余连接
本题的目的是找出多出来的那条边，其实也是用到并查集的原理，如果在题目中所说的树里，两个节点的根一样，那就不用再相连了，那就是说明这条边就是冗余的边，代码实现很简单，就是并查集的模板加剩余的处理，具体实现代码如下：
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int N=sc.nextInt();
Bcj bcj=new Bcj(N+1);
for(int i=0;i<N;i++){
int s=sc.nextInt();
int t=sc.nextInt();
if(bcj.isSame(s,t)){
System.out.println(s+" "+t);
}else{
bcj.join(s,t);
}
}
}
}
class Bcj{
private int[] father;
public Bcj(int N){
father=new int[N];
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 n,int m){
n=find(n);
m=find(m);
if(n==m) return;
father[m]=n;
}
public boolean isSame(int n,int m){
n=find(n);
m=find(m);
return n==m;
}
}冗余连接II
文章链接：代码随想录
题目链接：109. 冗余连接II
这道题研究了之后看题解也是直接放弃的程度