[백준][Python] 7511번 소셜 네트워킹 어플리케이션 - 코팩

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

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

풀이

기존 bfs 알고리즘을 사용할 시에 시간초과가 일어난다. 주어지는 유저의 수가 n^6까지 주어지기 때문이다.

그래서 분리 집합 알고리즘을 이용해서 답을 구해주었습니다.

bfs를 사용하게 되면 확인해야하는 친구 관계의 개수만큼 bfs가 돌아가기에 매우 비효율적입니다.

그러나 분리집합을 사용하게 되면 연결된 최상위 노드만이 저장된 리스트를 비교함으로 효율적으로 계산이 가능합니다. 

 

코드

# 7511번 소셜 네트워킹 어플리케이션
import sys
input = sys.stdin.readline

scene_num = 1
def find_parent(j):
    if parents[j] != j:
        parents[j] = find_parent(parents[j])
    return parents[j]

def union(p1, p2):
    p1 = find_parent(p1)
    p2 = find_parent(p2)
    if p1 > p2:
        parents[p1] = p2
    else:
        parents[p2] = p1

t = int(input())
for _ in range(t):
    n = int(input())
    r1 = int(input())
    parents = [i for i in range(n+1)]
    
    for _ in range(r1):
        a, b = map(int, input().split())
        if parents[a] != parents[b]:
            union(a, b)

    print(f"Scenario {scene_num}:")
    r2 = int(input())
    
    for _ in range(r2):
        a, b = map(int, input().split())
        if find_parent(a) == find_parent(b):
            print(1)
        else:
            print(0)

    print()
    scene_num += 1

 

출력결과