[PS] BOJ 1707이분 그래프

BOJ-1707 이분그래프

아래의 사이트는 이분그래프를 판별하는 문제이다.

https://www.acmicpc.net/problem/1707

본 문제는, DFS 탐색을통해 Vertex를 색칠해가면서 색칠이 완성되면 이분그래프임을 확인하는 문제이다. 이분그래프 알고리즘에 대해선 Bipartite Graph 글을 참고하자.

주의할점은 ,그래프가 유향 그래프일 경우에는 한쪽방항만(src->dest) 연결 정보를 가지고있으면 되지만,
무향 그래프일 경우에는 dest -> src 의 경우도 정보를 가지고 있어야 함을 유의하자.

아래의 소스에서 push_back 부분을 참고하자.

#include<iostream>
#include<vector>
#include<memory.h>
#define MAXV 20001      //MAX_VERTEX_COUNT
using namespace std;
 
vector<int> G[MAXV];  //Graph
int C[MAXV];            //Color
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;           //Vertex, Edge
    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.