[BOJ1707] 이분 그래프

이분 그래프인지 아닌지 판별

• 정점 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 이분 그래프라고 부름
• 그래프가 입력으로 주어질 때, 이분 그래프 판별

입력

• 테스트 케이스 수 K (2 <= K <= 5)
• 그래프 정점 개수 V (1 <= V <= 20000)
• 간선 개수 E (1 <= E <= 200000)

출력

• K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO 순서대로 출력

설계

• 그래프를 벡터로 구성하고, dfs를 이용해 방문하는 depth 순으로 0, 1 이분
• 다음 노드로 이동할 때, 이미 거쳐간 노드가 현재 이분 된 값과 같으면 NO
• 위 조건에 부합하지 않고 dfs끝나면 YES

피드백

• 방문을 단순히 visit을 이용하여 처리 가능 (-1 : 미방문 / 0,1 : 이분)
• 여러 케이스가 있기 때문에, 케이스 시작 전 visit 배열(-1), map, result 초기화 필요

How I solved(click to github)

---

ref :
BOJ1707