|
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
def DFS(v) :
global flag
for next in V[v] :
if C[next] == 0 :
C[next] = - C[v]
DFS(next)
elif C[next] == C[v] :
flag = False
k = int(input())
for i in range(k) :
Vn, En = map(int, input().split())
V = [[] for i in range(Vn + 1)]
C = [0 for i in range(Vn + 1)]
for i in range(En) :
v1, v2 = map(int, input().split())
V[v1].append(v2)
V[v2].append(v1)
flag = True
i = 0
while flag and i < Vn :
i = i + 1
if C[i] == 0 :
C[i] = 1
DFS(i)
if flag :
print('YES')
else :
print('NO')
|
점과 선의 수를 인풋받고,각각의 선을 따라 점의 연결정보를 V에 기록한다.
각 점이 이분집합의 어느 부분에 속할건지 기록하는 리스트 C를 만든다. (왼쪽 1, 오른쪽 -1, 미방문 0)
DFS의 실행점 now와 연결된 모든 점 next에 대해, C[next]가 아직 0이라면 now와 반대편 집합에 넣고 재귀한다.
재귀 중 now와 next가 같은 이분집합에 속하는 경우가 생긴다면 반복을 종료하고 NO를 출력한다.
그렇지 않고 모든 점을 다 1과 -1의 두 집합에 양분했다면 YES를 출력한다.
'Week 01 ~ 04 : 알고리즘 문제 풀이' 카테고리의 다른 글
| 파이썬 백준 2617 구슬 찾기 (0) | 2021.11.23 |
|---|---|
| 파이썬 백준 14888 연산자 끼워넣기 (0) | 2021.11.23 |
| 파이썬 백준 21606 아침 산책 (0) | 2021.11.21 |
| 파이썬 백준 11725 트리의 부모 찾기 (0) | 2021.11.21 |
| 파이썬 백준 2294 동전 2 (0) | 2021.11.20 |