Bipartite Graph
https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 문제 설명에 나와있듯이, 이분 그래프란 "그래프의 정점을 두 개의 집합으로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있는" 그래프입니다. 이를 만족하기 위해서 그래프의 인접한 두 정점은 서로 다른 집합에 속해야 합니다. 예를 들어, 왼쪽과 같은 그래프가 있습니다. 각 노드는 빨간/파란색인데, 이 색은 집합을 나타냅니다. 왼쪽의 그래프는 사실 오른쪽 그래프로 변환 가능합..
알고리즘
2022. 11. 14. 20:35