[백준]7511. 소셜 네트워킹 어플리케이션 (Java)

💡 문제 분석

/**
 *  10만명이라서 플로이드는 안될 것 같고,
 *  유니온 파인드로 친구관계를 서치하면 되겠다
 */

---

⌨️ 코드

JAVA

import java.io.*;
import java.util.*;

public class Q7511 {
    static int N, K, M;
    static int[] parent;
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = stoi(br.readLine());
        for(int t = 1; t <= tc; t++) {
            N = stoi(br.readLine());
            K = stoi(br.readLine());
            parent = new int[N];
            Arrays.fill(parent, -1);
            StringBuilder sb = new StringBuilder();

            for(int i = 0; i < K; i++) {
                st = new StringTokenizer(br.readLine());
                int a = stoi(st.nextToken());
                int b = stoi(st.nextToken());
                union(a, b);
            }

            M = stoi(br.readLine());
            sb.append(String.format("Scenario %d:%n", t));
            for(int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                int u = stoi(st.nextToken());
                int v = stoi(st.nextToken());
                if(find(u) == find(v))
                    sb.append(1).append("\n");
                else
                    sb.append(0).append("\n");
            }
            System.out.println(sb);
        }
    }

    public static int find(int n) {
        if(parent[n] < 0)
            return n;
        return parent[n] = find(parent[n]);
    }

    public static void union(int u, int v) {
        u = find(u);
        v = find(v);
        if(u == v)
            return;
        if(parent[u] < parent[v]) {
            parent[u] += parent[v];
            parent[v] = u;
        } else {
            parent[v] += parent[u];
            parent[u] = v;
        }
    }

    public static int stoi(String s) {
        return Integer.parseInt(s);
    }
}

Uploaded by Notion2Tistory v1.1.0