[BOJ_7511] 소셜 네트워킹 어플리케이션

설명

---

이번에도 일반적인 분리 집합 문제입니다. 이제는 연결되는 것에 대해서 검증하는 문제들은 거의 다 유니온 파인드를 사용해서 풀 수 있는데요. 웰노운 알고리즘이다 보니 연습용으로 풀기에 좋은 문제입니다.

 

풀이는 간단합니다. 문제에서 요구하는 연결을 한 후 추후에 연결 검증을 진행하면 됩니다.

 

이제 부터는 disjoint_set은 그만 풀고 다른 웰노운 알고리즘을 파봐야 겠습니다.

코드

---

package BOJ.disjoint_set;

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

public class BOJ_7511 {
    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer tk = new StringTokenizer(in.readLine()," ");
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(tk.nextToken());

        for (int t = 1; t <= T; t++){
            tk = new StringTokenizer(in.readLine()," ");
            int N = Integer.parseInt(tk.nextToken());
            int[] parent = new int[N];
            for (int i = 0 ; i < N; i++){
                parent[i] = i;
            }
            tk = new StringTokenizer(in.readLine()," ");
            int K = Integer.parseInt(tk.nextToken());

            for(int k = 0; k < K; k++){
                tk = new StringTokenizer(in.readLine()," ");
                int a = Integer.parseInt(tk.nextToken());
                int b = Integer.parseInt(tk.nextToken());
                union(a,b,parent);
            }
            sb.append("Scenario ").append(t).append(":").append("\n");
            int m = Integer.parseInt(in.readLine());
            for (int i = 0; i < m; i++){
                tk = new StringTokenizer(in.readLine()," ");
                int a = Integer.parseInt(tk.nextToken());
                int b = Integer.parseInt(tk.nextToken());
                sb.append(find(a,b,parent) + "\n");
            }
            sb.append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

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

    private static int find(int a, int b, int[] parent) {
        int rootA = getParent(a, parent);
        int rootB = getParent(b, parent);
        if(rootA == rootB){
            return 1;
        }else{
            return 0;
        }
    }

    private static int getParent(int a,int[] parent){
        if(parent[a] == a){
            return a;
        }else{
            return parent[a] = getParent(parent[a], parent);
        }
    }
}

 

Link

---

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