두 노드가 같은 그래프에 속해있는지 확인하는 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;
}
}
}