백준 24391 - 귀찮은 해강이

문제

https://www.acmicpc.net/problem/24391

리뷰

유니온 파인드 연산을 이용하여 풀 수 있는 단순한 문제였다.

관계를 받아 연결된 건물끼리 union 연산을 통해 같은 집합에 속하도록 설정해준 후
강의 시간표의 건물들을 하나씩 받으며 parent값이 다른 경우를 카운팅해주면 된다.

로직의 시간복잡도는 가장 복잡도가 큰 $O(N(a(N))$으로 수렴하므로 $N=100,000$인
최악의 경우에도 제한 조건 0.5초를 무난히 통과한다.

코드

import java.util.*;
import static java.lang.Integer.parseInt;

public class Main{
    static int[]parent;

    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        StringTokenizer st=new StringTokenizer(in.nextLine());

        int N=parseInt(st.nextToken());
        int M=parseInt(st.nextToken());

        parent=new int[N+1];
        Arrays.fill(parent, -1);

        while(M-->0){ //O(M(a(N))
            st=new StringTokenizer(in.nextLine());
            int u=parseInt(st.nextToken());
            int v=parseInt(st.nextToken());

            union(u, v);
        }

        st=new StringTokenizer(in.nextLine());
        int pre=find(parseInt(st.nextToken()));
        int count=0;

        while(st.hasMoreTokens()){ // O(N(a(N))
            int r=find(parseInt(st.nextToken()));
            if(pre!=r) count++;
            pre=r;
        }

        System.out.print(count);
    }

    static int find(int u){
        if(parent[u]<0) return u;

        return parent[u]=find(parent[u]);
    }

    static void union(int u, int v){
        int r1=find(u);
        int r2=find(v);

        if(r1==r2) return;

        if(parent[r1]<parent[r2]){
            parent[r1]+=parent[r2];
            parent[r2]=r1;
        }else{
            parent[r2]+=parent[r1];
            parent[r1]=r2;
        }
    }
}

결과