기록방

👉 문제링크 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 🔸 문제 분석 🔸 무방향 그래프가 주어지면, 이분 그래프인지 아닌지 판별한다. 🔸 문제 풀이 🔸 그래프 탐색을 통해 각 노드가 서로 다른 집합에 속하는지 구분한다. DFS로 처음 방문한 노드에 한번은 A집합, 한번은 B집합으로 번갈아 가며 포함시킨다. 이미 방문한 노드인데, 같은 집합이면 이분 그래프가 아니다. 여러 개의 부분 그래프로 이루어 져있을 수 있으므로, 모든 노드에서 DFS를 시작해본다. 모든 탐색 이후 이분 그래프 판정 결과를 출력한다...