[백준 1707] 이분 그래프

0. 제목

• 백준 1707 이분 그래프
• BOJ 1707 이분 그래프
• C++ 1707 이분 그래프

---

1. 문제

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

---

2. 풀이

• DFS, BFS 두가지 방법으로 풀 수 있다.
• 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다고 문제에 정의되어 있다.
• 각 단계마다 색을 칠하는데 color 가 0이면 아직 방문하지 않은 것이고 1과 2로 색을 표현하였다.
• 이분 그래프 여부를 판단하는 함수에서는 다음 단계로 갈때 같은 색깔을 가지고 있으면 false를 반환하고 그것이 아니면 true를 반환하도록 하였다.

 

---

3. 코드

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
 
vector<int> connect[20001];
int nodeColor[20001];
int K, V, E;
 
void dfs(int nodeNum, int color);
bool isBipartite(void);
 
int main(int argc, const char * argv[]) {
    int a, b;
    
    cin >> K;
    
    for(int i = 0; i < K; i++){
        for (int j = 1; j < 20001; j++)
            connect[j].clear(); // 케이스마다 초기화시켜줘야 함
        memset(nodeColor, 0, sizeof(nodeColor)); //케이스마다 초기화시켜줘야 함
        
        cin >> V >> E;
        for(int j = 0; j < E; j++){
            cin >> a >> b;
            connect[a].push_back(b);
            connect[b].push_back(a);
        }
        
        for(int j = 1; j <= V; j++){
            if(nodeColor[j] == 0)
                dfs(j, 1); // 1번 색깔부터 시작
        }
        
        if(isBipartite())
            cout << "YES" << '\n';
        else
            cout << "NO" << '\n';
    }
    
    return 0;
}
 
//color 가 0 이면 아직 방문하지 않은 것이고 1, 2 를 각 색깔로 둔다.
void dfs(int nodeNum, int color){
    nodeColor[nodeNum] = color;
    unsigned long int size = connect[nodeNum].size();
    for(unsigned long int i = 0; i < size; i++){
        int next = connect[nodeNum][i];
        if(!nodeColor[next])
            dfs(next, 3 - color);
    }
}
 
bool isBipartite(void){
    for(int i = 1; i <= V; i++){
        unsigned long int size = connect[i].size();
        for(unsigned long int j = 0; j < size; j++){
            int next = connect[i][j];
            if(nodeColor[i] == nodeColor[next])
                return false;
        }
    }
    return true;
}