Day56 图论part06
108.冗余连接
并查集应用类题目,关键是如何把题意转化成并查集问题
代码随想录
import java.util.Scanner;
public class Main{
public static void main (String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
DisJoint disjoint = new DisJoint(n+1);
while(n-- > 0){
int a = scanner.nextInt();
int b = scanner.nextInt();
if(disjoint.isSame(a, b)){
System.out.println(a+" "+b);
break;
}else{
disjoint.join(a, b);
}
}
}
}
class DisJoint{
private int[] farther;
public DisJoint(int N){
farther = new int[N];
for(int i = 0; i < N; i++){
farther[i] = i;
}
}
public int find(int n){
if(n == farther[n]){
return n;
}else{
return farther[n] = find(farther[n]);
}
// return n == farther[n] ? n : (farther[n] = find(farther[n]));
}