백준 7511: 소셜 네트워킹 어플리케이션 java/자바

두 노드가 같은 그래프에 속해있는지 확인하는 union-find 알고리즘 활용해 풀었다.

package Baekjoon.boj7511;

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

public class Main {
    static int N,K,M;
    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;
        int T = Integer.parseInt(br.readLine());

        for (int i = 1; i <= T; i++) {
            sb.append("Scenario ").append(i).append(":").append("\n");
            N = Integer.parseInt(br.readLine());
            K = Integer.parseInt(br.readLine());
            parent = new int[N];

            for (int j = 0; j < N; j++) {
                parent[j] = j;
            }

            for (int j = 0; j < K; j++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());

                union(a,b);
            }

            M = Integer.parseInt(br.readLine());
            for (int j = 0; j < M; j++) {
                st = new StringTokenizer(br.readLine());
                int u = Integer.parseInt(st.nextToken());
                int v = Integer.parseInt(st.nextToken());

                if (find(u) == find(v)) {
                    sb.append(1).append("\n");
                } else {
                    sb.append(0).append("\n");
                }
            }
            sb.append("\n");
        }

        System.out.println(sb.toString());
    }

    static int find(int a) {
        if (a == parent[a]) {
            return a;
        } else {
            return parent[a] = find(parent[a]);
        }
    }

    static void union(int a, int b) {
        int A = find(a);
        int B = find(b);
        if (A < B) {
            parent[B] = A;
        } else {
            parent[A] = B;
        }
    }

}