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

🐸 문제 정보

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

 

🤖 알고리즘

유니온 파인드

 

⏱️ 풀이 시간

16.43m

 

📝 풀이

유니온 파인드의 정석같은 문제였다.

그래프가 연결되어있는지 찾아야하는데, 시간이 조금 걸렸던 이유는

마지막에 parent[a]와 parent[b]를 비교했다..

find(a)와 find(b)로 고쳐서 통과할 수 있었다.

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

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

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

for i in range(int(input().rstrip())):
    n, k = int(input().rstrip()), int(input().rstrip())
    parent = [i for i in range(n)]
    for _ in range(k):
        a, b = list(map(int, input().rstrip().split()))
        if find(a) != find(b): union(a, b)
    print(f'Scenario {i + 1}:')
    for _ in range(int(input().rstrip())):
        a, b = list(map(int, input().rstrip().split()))
        if find(a) == find(b):
            print(1)
        else:
            print(0)
    print()