알고리즘/sw
[SW Expert Academy] 5102번 노드의 거리 python
HAN_PY
2020. 5. 26. 14:59
반응형
문제의 저작권은 SW Expert Academy에 있습니다.
수업에서 같은 조에 참여하고 싶은 사람끼리 두 사람의 출석 번호를 종이에 적어 제출하였다.
한 조의 인원에 제한을 두지 않았기 때문에, 한 사람이 여러 장의 종이를 제출하거나 여러 사람이 한 사람을 지목한 경우 모두 같은 조가 된다.
예를 들어 1번-2번, 1번-3번이 같은 조가 되고 싶다고 하면, 1-2-3번이 같은 조가 된다. 번호를 적지도 않고 다른 사람에게 지목되지도 않은 사람은 단독으로 조를 구성하게 된다.
1번부터 N번까지의 출석번호가 있고, M 장의 신청서가 제출되었을 때 전체 몇 개의 조가 만들어지는지 출력하는 프로그램을 만드시오.
[입력]
첫 줄에 테스트 케이스의 개수가 주어지고, 다음 줄부터 테스트 케이스 별로 첫 줄에 N과 M, 다음 줄에 M 쌍의 번호가 주어진다. 2<=N<=100, 1<=M<=100
[출력]
각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.
풀이
T = int(input())
def findSet(x):
if x == parent[x]: return x
else: return findSet(parent[x])
for tc in range(1, T + 1):
N, M = map(int, input().split())
arr = list(map(int, input().split()))
parent = list(range(N + 1))
for i in range(M):
a = arr[2 * i]
b = arr[2 * i + 1]
parent[findSet(b)] = findSet(a) # b의 대표 원소를 a의 대표원소로 교체
cnt = 0
for i in range(1, N + 1): # 대표원소가 자기 자신인 경우의 수
if parent[i] == i:
cnt += 1
print('#{} {}'.format(tc, cnt))
만약 그래프 개념이 약하다면 알고리즘의 그래프 부분 보고 오자
반응형