[SWEA/Python] 7465. 창용 마을 무리의 개수

📌 문제

https://swexpertacademy.com/main/main.do

SW Expert Academy

 

📌 문제 접근 방법

1. 어제 풀었던 그룹 나누기와 똑같은 방식의 풀이!
2. 이번엔 다른 코드 참고 안하고 직접 제대로 구현해봤다.

 

📌 코드

import sys
sys.stdin = open('input.txt')

def find_leader(p):
    if p != leader[p]:
        leader[p] = find_leader(leader[p])
    
    return leader[p]


def know(p1, p2):
    l1 = find_leader(p1)
    l2 = find_leader(p2)

    if rank[l1] >= rank[l2]:
        leader[l2] = l1

        if rank[l1] == rank[l2]:
            rank[l1] += 1
    
    else:
        leader[l1] = l2


T = int(input())

for t in range(1, T+1):
    N, M = map(int, input().split())

    leader = [x for x in range(N+1)]
    rank = [0 for _ in range(N+1)]

    for _ in range(M):
        person1, person2 = map(int, input().split())
        know(person1, person2)

    for i in range(N+1):
        find_leader(i)
    
    print('#{} {}'.format(t, len(set(leader))-1))