6124 : 이분 그래프
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
그래프의 모든 정점을 두 개의 독립된 그룹으로 나누어, 모든 간선의 양 끝 정점이 서로 다른 그룹에 속하도록 칠할 수 있는 그래프를 이분 그래프(Bipartite Graph)라고 부릅니다.
그래프 정보가 주어졌을 때 이분 그래프인지 판별하는 프로그램을 작성하십시오.
그래프 정보가 주어졌을 때 이분 그래프인지 판별하는 프로그램을 작성하십시오.
입력 설명
첫째 줄에 테스트케이스의 개수 T가 주어집니다.
각 테스트케이스의 첫째 줄에 정점 수 V (1 ≤ V ≤ 1,000)와 간선 수 E (1 ≤ E ≤ 10,000)가 주어집니다.
이후 E개의 줄에 걸쳐 간선 정보 u v가 주어집니다.
각 테스트케이스의 첫째 줄에 정점 수 V (1 ≤ V ≤ 1,000)와 간선 수 E (1 ≤ E ≤ 10,000)가 주어집니다.
이후 E개의 줄에 걸쳐 간선 정보 u v가 주어집니다.
출력 설명
각 테스트케이스 순서대로 이분 그래프이면
YES, 아니면 NO를 줄을 바꾸어 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
2
3 2
1 3
2 3
3 3
1 2
2 3
3 1
출력 예시
COPY
복사되었습니다!
복사되었습니다!
YES
NO
도움
임의의 정점에서 시작해 색상 1로 칠하고, 인접한 정점들은 색상 -1로 번갈아가며 BFS 칠하기를 진행합니다. 이미 칠해진 인접 정점의 색이 나와 동일하다면 이분 그래프가 될 수 없습니다.