백준 7511 [소셜 네트워킹 어플리케이션] 파이썬

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

 

# 백준 7511 소셜 네트워킹 어플리케이션
# Union-Find (Disjoint Set Union) 알고리즘으로 연결 관계 처리

import sys
sys.setrecursionlimit(10**6)   # 재귀 깊이 제한 (find 함수에서 재귀 사용 가능성 대비)
input = sys.stdin.readline

T = int(input())  # 테스트 케이스 개수


# find 연산 (경로 압축)
# x의 루트(대표 노드)를 찾아 반환
def find(x):
    if x != parent[x]:
        parent[x] = find(parent[x])  # 경로 압축: 루트로 바로 연결
    return parent[x]


# union 연산
# 두 집합을 합침 (루트를 하나로 연결)
def union(a, b):
    a = find(a)
    b = find(b)
    if a != b:
        parent[a] = b


# 연결 여부 확인
def is_con(a, b):
    return find(a) == find(b)


# 각 테스트 케이스 처리
for i in range(1, T + 1):
    n = int(input())  # 사용자 수
    parent = [i for i in range(n + 1)]  # 부모 초기화 (자기 자신을 부모로 설정)

    k = int(input())  # 친구 관계 개수
    for _ in range(k):
        a, b = map(int, input().split())
        union(a, b)  # 친구 관계를 통해 두 사용자 집합 합치기

    m = int(input())  # 쿼리 개수
    print("Scenario {}:".format(i))  # 시나리오 번호 출력

    for _ in range(m):
        a, b = map(int, input().split())
        # 두 사용자가 같은 집합(=소셜 네트워크)인지 확인
        print(int(is_con(a, b)))  # True면 1, False면 0 출력
    
    print()  # 각 시나리오 출력 사이에 공백 줄