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

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

7511번: 소셜 네트워킹 어플리케이션

문제

백준 7511번 소셜 네트워킹 어플리케이션

 

처음으로 Union find알고리즘을 사용해 본 문제다.

 

문제에 테스트 케이스를 입력받는다 라는 말이 없어서 입력이 헷갈렸던 문제다. 질문 게시판을 보니 나와 같은 사람이 있었다.

 

문제는 각 테스트 케이스에서

 

유저 수

친구 관계 수

친구 관계

친구 관계 검사 수

친구 관계 검사

 

이렇게 입력을 받는다.

 

a라는 유저가 b라는 유저를 친구 관계를 타고 타고 넘어가서 찾을 수 있는지 없는지를 출력하는 문제다.

 

각 관계를 그래프로 나타내고, 각 그래프들이 연결되어 있는지 확인하면 되는 문제. 그냥 Union find 써주세요 문제다.

 

Union find는 이론만 보고 실제로 구현해 본적은 없었는데, 생각보다 간단한 알고리즘이었다.

 

 

정답

import sys

def find_root(parent, x) :
    if parent[x] != x :
        return find_root(parent, parent[x])
    return x

def union(parent, a, b) :
    a = find_root(parent, a)
    b = find_root(parent, b)
    if a < b :
        parent[b] = a
    else :
        parent[a] = b

input = sys.stdin.readline

testcase = int(input())


for i in range(testcase) :
    n = int(input())
    parent = [j for j in range(n)]

    friend_relationship_num = int(input())

    for j in range(friend_relationship_num) :
        s, e = map(int, input().split())
        union(parent, s, e)
    
    search_num = int(input())
    ans = []
    for j in range(search_num) :
        start, find = map(int, input().split())
        if find_root(parent, start) == find_root(parent, find) :
            ans.append(1)
        else :
            ans.append(0)
    print("Scenario {}:".format(i+1))
    for a in ans :
        print(a)
    print()