[BOJ_17352] 여러분의 다리가 되어 드리겠습니다!

설명

---

다리 두개를 단순히 연결해서 N - 2개의 다리 상태에서 N - 1의 다리 상태로 모두 이어 질 수 있는 방안을 출력하면 되는 문제입니다. 단순히 분리집합을 이용해서 합집합끼리 묶고 남은 root 위치의 위치 값은 나눠진 것이니 이것을 연결 해줍니다.

 

위 설명이 바로 이해가 되지 않는다면 disjoint_set 자체에 대해서 조금 더 공부하시면 바로 이해 하기가 쉽습니다. 

 

 

코드

---

 

package BOJ.disjoint_set;

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

public class BOJ_17352 {
    static int[] parent;
    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine()," ");

        int N = Integer.parseInt(tk.nextToken());
        parent = new int[N + 1];
        for (int i = 1; i <= N; i++){
            parent[i] = i;
        }

        for (int i = 0; i < N - 2; i++){
            tk = new StringTokenizer(in.readLine()," ");
            int a = Integer.parseInt(tk.nextToken());
            int b = Integer.parseInt(tk.nextToken());
            union(a,b);
        }
        findRoot();
    }

    private static void findRoot() {
        int cnt = 0;
        for (int i = 1; i < parent.length; i++){
            if(parent[i] == i){
                cnt++;
                System.out.print(i + " ");
                if(cnt >= 2){
                    break;
                }
            }
        }
    }

    private static int getParent(int a){
        if(parent[a] == a){
            return a;
        }else{
            return parent[a] = getParent(parent[a]);
        }
    }
    private static void union(int a, int b) {
        int rootA = getParent(a);
        int rootB = getParent(b);
        if(rootA != rootB){
            parent[rootA] = rootB;
        }
    }
}

 

Link

---

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