그래프가 이분그래프인지 아닌지를 판단하는 문제이다.
이 문제를 풀기전에 이분그래프가 뭔지 알아야한다.
같은 집합에 있는 정점들은 서로 인접하지 않아야 한다는 규칙이 있다.
1,4,5 가 같은 집합 2,3,6이 같은 집합으로 같은 집합안에 있는 정점들은 서로 인접해있지 않다는 것이다.
그러면 이분그래프인지 아닌지는 어떻게 판단하나.?
인접해 있는 정점들은 서로 색깔이 다르다고 생각하면 된다.
이것도 뭐냐면 위 그림에서 1정점에서 인접해 있는 정점들은 6,2,3, 인데 1이 빨간색이라면 6,2,3 은 검은색 이여야 한다.
그다음 6이 검은색이면 인접해 있는 4는 빨간색이여야 한다.
여기서 4는 빨간색인데 아까 색칠했던 2는 검은색이였다. 만약 여기서 4와 2가 같은 색깔이라면 이분그래프가 될수 없다는 것이다.
이논리로 짠 코드는 이렇다.
import sys
from collections import deque
k = int(input())
def BFS_queue(first):
Color[first]="B"
visited[first] = 1
queue=deque()
queue.append(first)
while queue:
v = queue.popleft()
visited[v] = 1
if Color[v] == 'B':
for i in graph[v]:
if visited[i] == 0:
queue.append(i)
visited[i] = 1
if Color[i] == "B":
return 0
else:
Color[i] = "R"
else:
for i in graph[v]:
if visited[i] == 0:
queue.append(i)
visited[i]=1
if Color[i] == "R":
return 0
else:
Color[i] = "B"
return 1
for _ in range(k):
v, e = map(int, sys.stdin.readline().split())
graph = [[] for i in range(v + 1)]
visited = [0 for i in range(v + 1)]
result = set()
for _ in range(e):
start, end = map(int, sys.stdin.readline().split())
graph[start].append(end)
graph[end].append(start)
result.add(start)
result.add(end)
for i in result:
Color = ["" for i in range(v + 1)]
if BFS_queue(i) == 0:
print("NO")
break
else:
print("YES")처음에 풀기는 어렵지 않았다.
근데 틀렸다고 뜨더니, 수정하고나니 시간초과가 났다.
왜냐.
일단 그래프가 연결되어있는 경우에는 정점 한곳에서만 위의 알고리즘을 실행해도 이분그래프인지 아닌지를 판단할수있다.
하지만 그래프가 연결되어있지 않은 경우에는 처음 그래프에서 이분그래프이고 떨어져있는 그래프가 이분그래프가 아니여도 결과로는 이분그래프라고 나올것이다.
이렇게 되면 안되기에 정점들을 연결해줄때 그 간선의 처음과 시작정점을 새로운 집합변수에 넣어주고 그 집합변수를 시작으로 모든 정점을 탐색하면 되는것이다.
연결되어있지 않은 경우에도 모든경우에서 한번이라도 No가 뜨면 no 이고 No가 한번도 안뜨면 Yes 를 출력할것이다.
시간초과가 떠서 줄이고 줄였는데 그냥 딱 뭐때문에 시간초과를 해결한지는 모르겠는데 코드를 줄이고 줄이다 보니 시간초과가 풀린,,, 미스테리한 문제
