목록이분그래프 (1)

One_Blog

백준 1707 - 이분 그래프

백준 골드 4 이분 그래프 문제이다. 다음과 같은 그래프가 주어지면 해당 그래프가 이분 그래프인지 아닌 지 판별하는 문제이다. 이분 그래프란, 그래프의 정점 집합을 둘로 분할하여, 각 집합에 속한 정점끼리 서로 인접하지 않도록 분할할 수 있는 그래프를 의미한다. 이런식..?인데, 파랑끼리 연결 안되고, 빨강끼리 연결 안된 거를 보면 된다. from collections import deque def is_bipartite(a, edges): color = [0] * (a + 1) visited = [False] * (a + 1) for v in range(1, a + 1): if visited[v]: continue stack = deque([(v, 1)]) while stack: vertex, c = ..
알고리즘 2023. 6. 21. 17:18
이전 Prev 1 Next 다음