[백준 문제] 1707번 이분 그래프 (파이썬)
문제풀이
- dfs 함수를 만들어서 그룹A와 그룹B를 나누는 color리스트를 만든다.
- 간선들간의 관계에서 color가 같은 것들이 연결 되어 있으면 NO를 출력하면 된다.
- 백준에서는 역시 시간 초과가 뜨는데, 이유가 만약 재귀함수 문제라면 맞은것으로 간주하려고한다…
def dfs(node, c) : # C에서 0 : 방문X, 1 : 그룹A, 2 : 그룹B
color[node] = c
for i in range(len(a[node])):
next = a[node][i]
if color[next] == 0 :
dfs(next, 3-c)
K = int(input())
for i in range(K) :
# V,E = 정점개수, 간선개수
V, E = map(int, input().split())
a = []
for _ in range(V+1) :
a.append([])
for _ in range(E) :
x, y = map(int, input().split())
a[x].append(y)
a[y].append(x)
color = [0]*(V+1)
dfs(1,1)
ok = True
for i in range(1, V+1) :
for l in range(len(a[i])) :
j = a[i][l]
if color[i] == color[j] :
ok = False
if ok == True :
print('YES')
elif ok == False :
print('NO')
2
3 2
1 3
2 3
YES
4 4
1 2
2 3
3 4
4 2
NO
그냥 문제풀기 위해 테스트 한 것들
V, E = 3, 2
a = [[],[3],[3],[1,2]]
color = [0,0,0,0]
V, E = 4, 4
a = [[],[2],[1,3,4],[2,4],[2,3]]
color = [0,0,0,0,0]
def dfs(node, c) : # C에서 0 : 방문X, 1 : 그룹A, 2 : 그룹B
color[node] = c
for i in range(len(a[node])):
next = a[node][i]
if color[next] == 0 :
dfs(next, 3-c)
ok = True
for i in range(1, V+1) :
for l in range(len(a[i])) :
j = a[i][l]
if color[i] == color[j] :
print(i, j)
ok = False
if ok == True :
print('YES')
elif ok == False :
print('NO')
2
3 2
1 3
2 3
4 4
1 2
2 3
3 4
4 2
V, E = 3, 2
a = [[],[3],[3],[1,2]]
color = [0,0,0,0]
# K번 돌리기
K = int(input())
for i in range(K) :
# V,E = 정점개수, 간선개수
V, E = map(int, input().split())
a = []
for _ in range(V+1) :
a.append([])
for _ in range(E) :
x, y = map(int, input().split())
a[x].append(y)
a[y].append(x)
