BOJ-1707 이분그래프
아래의 사이트는 이분그래프를 판별하는 문제이다.
본 문제는, DFS 탐색을통해 Vertex를 색칠해가면서 색칠이 완성되면 이분그래프임을 확인하는 문제이다. 이분그래프 알고리즘에 대해선 Bipartite Graph 글을 참고하자.
주의할점은 ,그래프가 유향 그래프일 경우에는 한쪽방항만(src->dest) 연결 정보를 가지고있으면 되지만,
무향 그래프일 경우에는 dest -> src 의 경우도 정보를 가지고 있어야 함을 유의하자.
아래의 소스에서 push_back 부분을 참고하자.
#include<iostream>
#include<vector>
#include<memory.h>
#define MAXV 20001
using namespace std;
vector<int> G[MAXV];
int C[MAXV];
bool DFS(int v, int c) {
C[v] = c;
for (int i = 0; i < G[v].size(); i++){
if (C[G[v][i]] == c){
return false;
}
if (C[G[v][i]] == 0 && !DFS(G[v][i], (~c)+1)){
return false;
}
}
return true;
}
int main() {
int T;
int V, E;
cin >> T;
while (T--){
bool isBipartite = true;
memset(C, 0, sizeof(C));
memset(G, 0, sizeof(G));
cin >> V >> E;
for (int i = 0; i < E; i++){
int src, dest;
cin >> src >> dest;
G[src].push_back(dest);
G[dest].push_back(src);
if (src == dest){
isBipartite = false;
break;
}
}
for (int i = 0; i < V; i++){
if (C[i] == 0){
if (!DFS(i, 1)){
isBipartite = false;
break;
}
}
}
if (isBipartite == true){
cout << "YES" << endl;
}
else{
cout << "NO" << endl;
}
}
return EXIT_SUCCESS;
}
Copyright (C) 2016 (DaeHyun, Hwang) all rights reserved.