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

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

 

문제

어렸을때부터 컴퓨터 프로그래밍에 엄청난 소질을 보인 상근이는 항상 소셜 네트워킹 웹사이트를 만들고 싶어 했다. 상근이는 페이스북을 벤치마킹하기 위해 지난 3년간 열심히 사용을 했고, 이제 페이스북의 단점을 보완한 새 소셜 네트워킹 웹 2.0 어플리케이션을 만들려고 한다.

사람들은 소셜 네트워킹 어플리케이션에 가입을 한 다음, 현실에서 아는 사람을 친구로 추가하기 시작한다. 이러한 친구 관계 정보를 이용해 친구 관계 그래프를 그릴 수 있다.

소셜 네트워킹 어플리케이션에서 가장 중요한 기능은 한 사람이 다른 사람의 페이지를 방문했을 때, 친구 관계 그래프에서 두 사람 사이의 경로를 보여주는 기능이다. 경로가 없는 경우에는 보여주지 않는다.

상근이의 서비스는 매우 유명해졌고, 위의 기능은 사람들이 점점 많아질수록 경로를 구하는 시간이 매우 느려지게 되었다. 그 이유는 두 사람 사이의 경로가 없는 경우에 경로를 찾기 위해 너무 오랜시간 그래프를 탐색하기 때문이었다. 따라서, 상근이는 두 사람 사이의 경로가 존재하는지 안 하는지를 미리 구해보려고 한다.

유저의 수와 각 유저의 친구 관계가 입력으로 주어진다. 이때, 주어지는 두 사람이 친구 관계 그래프상에서 경로가 존재하는지 안 하는지를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 유저의 수 1 ≤ n ≤ 106이 주어진다. 둘째 줄에는 친구 관계의 수 1 ≤ k ≤ 105가 주어진다. 다음 k개 줄에는 두 정수 0 ≤ a, b < n이 주어진다. 두 수는 친구 관계를 나타내며, 유저 a와 b가 친구라는 소리이다. 다음 줄에는 미리 구할 쌍의 수 1 ≤ m ≤ 105가 주어진다. 다음 m개 줄에는 구해야하는 쌍을 나타내는 u, v가 주어진다.

출력

각 테스트 케이스마다 "Scenario i:"를 출력한다. i는 테스트 케이스 번호이며, 1부터 시작한다. 그 다음, 각각의 쌍마다 두 사람을 연결하는 경로가 있으면 1, 없으면 0을 출력한다.

각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

 

코드

import sys
input = sys.stdin.readline

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

def union_parent(a, b, parent):
    a = find_parent(a, parent)
    b = find_parent(b, parent)
    
    if a == b:
        return
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

for i in range(int(input())):
    n = int(input())    # 유저 수
    parent = [i for i in range(n)]
    
    for _ in range(int(input())):
        a, b = map(int, input().split())    # a와 b가 친구
        union_parent(a, b, parent)
        
    print("Scenario " + str(i+1) + ":")    
    for _ in range(int(input())):
        u, v = map(int, input().split())
        if find_parent(u, parent) == find_parent(v, parent):
            print(1)
        else:
            print(0)
    print()