그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.
BLUE
표시한 뒤 이어지는 다음 정점은 RED
로 표시한다. 이런식으로 번갈아가면서 진행할 때, 이미 방문한 정점에 도달할 수 있다.#include <iostream>
#include <vector>
using namespace std;
static int K, N, M;
static bool ansflag;
static vector<int> graph[20001]; // 인접 리스트
static vector<int> group(20001, -1); // n번 정점이 속한 그룹
static vector<bool> isVisited(20001); // n번 정점 방문 여부
void dfs(int here, int g){
if (ansflag) return;
isVisited[here] = true;
group[here] = g;
for (const int& there : graph[here]) {
if (!isVisited[there]) dfs(there, (g + 1) % 2);
if (group[there] == group[here]) ansflag = true;
// 중요! 현재 정점과 연결된 다음 정점이 같은 그룹에 있으면 이분그래프가 아님!
}
}
void solve() {
for (int startVertex = 1; startVertex <= N; ++startVertex) {
if (!isVisited[startVertex]) dfs(startVertex, 0);
if (ansflag) break;
}
}
void clear() {
for (int i = 1; i <= N; ++i) graph[i].clear();
isVisited.assign(N + 1, false);
group.assign(N + 1, -1);
ansflag = false;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> K;
while(K--){
cin >> N >> M;
for (int i = 1; i <= M; ++i) {
int start = 0, end = 0;
cin >> start >> end;
graph[start].push_back(end);
graph[end].push_back(start);
}
solve(); // DFS를 이용한 이분그래프 판별.
if (!ansflag) cout << "YES" << '\n';
else cout << "NO" << '\n';
clear(); // 다음 loop를 위해 전역변수들 초기화하기.
}
}