이분 그래프
면접 대비시간 제한2초메모리 제한256 MB
여러 개의 무방향 그래프가 주어질 때 각 그래프를 두 그룹으로 나누어 같은 그룹 안에 변이 없도록 색칠할 수 있는지 판별합니다.
문제
무방향 그래프의 정점들을 두 집합으로 나누었을 때, 같은 집합에 속한 두 정점 사이에는 간선이 없게 만들 수 있으면 그 그래프를 이분 그래프라고 한다.
여러 그래프가 주어진다. 각 그래프가 이분 그래프인지 판별하라.
입력
첫째 줄에 테스트 케이스의 개수 K가 주어진다.
각 테스트 케이스의 첫 줄에는 정점 수 V와 간선 수 E가 공백으로 구분되어 주어진다. 정점은 1부터 V까지 번호가 붙어 있다.
이어서 E개의 줄에는 서로 인접한 두 정점 u, v가 공백으로 구분되어 주어진다. u와 v는 서로 다르다.
출력
각 테스트 케이스마다, 해당 그래프가 이분 그래프이면 YES를, 아니면 NO를 한 줄에 하나씩 출력한다.
제한
- 2 <= K <= 5
- 1 <= V <= 20,000
- 1 <= E <= 200,000