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]));}