문제링크

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

구현방법

기본적으로 각 배열이 존재함.

n은 100만개

m은 10만개

2중 돌면 터짐. -> O(N) 안쪽으로 생각해야함.

List 형식이 나은가

a와 b 가 같은 경우 합집합

1. 둘이 같은 원소일 때 굳이 합칠 필요가 있는가?
2. 없다고 생각하기 때문에 넘어감.

a와 b 가같은경우 ??

2중 ArrayList

그래프 만들듯이 진행하고 -> 여기서 for문이 엄청 돌아가게 된다는 것을 알게되어 포기

---

UnionFind 기초문제

• 둘이 묶으면 좋겠다는 생각이 들었지만 처음에 UnionFind 알고리즘은 생각이 나지 않았음.
• 부모가 같으면 같은 집합에 포함된다는 것을 이용해서 빠르게 구할 수 있음.

알고리즘

Union-Find

CODE

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {


    static int[] parent;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine());

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


        parent = new int[N+1];
        //전체 만들어두기 그리고 본인 포함 해두기
        for (int idx = 0; idx <= N; idx++) {
            parent[idx] = idx;
        }

        for (int test = 0; test < M; test++) {
            st = new StringTokenizer(br.readLine());
            int select = Integer.parseInt(st.nextToken());
            int first = Integer.parseInt(st.nextToken());
            int second = Integer.parseInt(st.nextToken());

            //0인 경우 둘다 포함
            if (select == 0) {
                if (first == second) {
                    continue;
                }
                union(first,second);
                //쌍방으로 넣어준다.
            } else {
                if (first == second) {
                    sb.append("YES").append("\n");
                    continue;
                }
                if(isSameParent(first,second)){
                    sb.append("YES").append("\n");
                }else
                    sb.append("NO").append("\n");
                //한쪽에만 포함되면 어쩌피 포함된거임.
            }
        }

        System.out.print(sb);
    }

    //부모가 같은지 체크 -> 같으면 같은 집합임.
    private static boolean isSameParent(int first, int second) {
        first = find(first);
        second = find(second);

        if(first == second){
            return true;
        }

        return false;
    }

    public static int find(int num){
        if(num == parent[num]){
            return num;
        }

        return parent[num] = find(parent[num]);
    }
    private static void union(int first, int second) {
        //각 부모 찾기
        first = find(first);
        second = find(second);

        if(first != second){
            if(first < second){
                parent[second] =first;

            }else{
                parent[first]= second;
            }
        }
    }
}