[이.취.코] Chap 10. 그래프 이론 - 팀 결성

@mildsalmon·2021-09-04 11:36

1. 팀 결성

난이도
- 중
풀이 시간
- 20분
시간 제한
- 2초
메모리 제한
- 128MB
기출
- 핵심 유형

A. 문제

학생에게 0부터 N번까지 번호를 부여했다.
모든 학생이 서로 다른 팀으로 구분되어 총 N+1개의 팀이 존재한다.
팀 합치기 연산과 같은 팀 여부 확인 연산을 사용할 수 있다.

팁 합치기
- 두 팀을 합치는 연산
같은 팀 여부 확인
- 특정 두 학생이 같은 팀에 속하는지 확인

a. 입력 조건

첫째줄에 N, M
- 1 <= N, M <= 100,000
다음 M개 줄에 각각 연산이 주어진다.
- 팀 합치기는 0 a b (a 학생 팀과 b 학생 팀을 합친다)
- 같은 팀 여부 확인 1 a b (a학생과 b학생이 같은 팀이지 확인)
  - a, b는 N 이하의 양의 정수

b. 출력 조건

같은 팀 여부 확인 연산에 대해 YES, NO를 한줄씩 출력

c. 테스트 케이스

입력 예시

출력 예시
```
NO
NO
YES
```

B. 내 답안


def find_team(team, x):  
    if team[x] != x:  
        team[x] = find_team(team, team[x])  
    return team[x]  
  
  
def union_team(team, a, b):  
    a = find_team(team, a)  
    b = find_team(team, b)  
  
    if a < b:  
        team[b] = a  
    else:  
        team[a] = b  
  
  
n, m = map(int, input().split())  
  
array = []  
team = [0] * (n + 1)  
  
for i in range(1, n + 1):  
    team[i] = i  
  
for i in range(m):  
    c, a, b = list(map(int, input().split()))  
    array.append([c, a, b])  
  
for i in range(m):  
    c, a, b = array[i]  
  
    if c == 0:  
        union_team(team, a, b)  
    elif c == 1:  
        if find_team(team, a) == find_team(team, b):  
            print("YES")  
        else:  
            print("NO")  
  
# 20분 4초 / Pass / Time out