ALGORITHM

[JAVA] 알고리즘 : 그리디- 친구인가? (Disjoint-Set : Union&Find)

연듀 2022. 11. 25. 16:20

import java.util.Scanner;

class Main{
    static int[] unf;
    public static int Find(int v){ // v번 학생의 집합 번호를 리턴
        if(v==unf[v]) return v;
        else return unf[v] = Find(unf[v]);
    }

    public static void Union(int a, int b){
        int fa = Find(a);
        int fb = Find(b);
        if(fa!=fb) unf[fa] = fb;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        unf = new int[n+1];

        for(int i=1; i<=n; i++) unf[i] = i;
        for(int i=1; i<=m; i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            Union(a, b); // a와 b를 한 집합으로
        }
        int a = sc.nextInt();
        int b = sc.nextInt();
        int fa = Find(a);
        int fb = Find(b);

        if(fa == fb) System.out.println("YES"); // a와 b가 친구면
        else System.out.println("NO");
    }
}