백준 이분 그래프 [c++]

이분 그래프 골드4

문제

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호 u, v (u ≠ v)가 빈 칸을 사이에 두고 주어진다.

출력

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

풀이

• 이분그래프 : 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프. https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html
• 인접한 정점은 같은 색으로 칠해지면 안된다.
• BFS로 같은 레벨은 같은 색으로 칠한다. 그리고 다 칠하고 나서 인접한 정점에 같은 색으로 칠해진 것이 있는지 확인.
• 색을 칠하는 state_change함수와 bipartite인지 확인하는 is_bipartite함수를 작성하여 해결.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

vector<int> graph[20001];
queue<int> q;
int visited[20001];

void init(){
    for(int i = 0; i < 20001; i++)
    {
        visited[i] = 0;
        graph[i].clear();
    }
}

int state_change(int state){
    if(state == 1) return 2;
    if(state == 2) return 1;
}

void bfs(int start){

    int state = 1;
    visited[start] = state;
    int size = graph[start].size();
    for(int i = 0; i < size; i++)
    {
        q.push(graph[start][i]);
    }

    while(!q.empty()){
        int q_size = q.size();
        state = state_change(state);
        for(int i = 0; i < q_size; i++)
        {
            if(visited[q.front()] == 0){
                visited[q.front()] = state;
                for(int j = 0; j < graph[q.front()].size(); j++)
                {   
                    if(visited[graph[q.front()][j]] == 0)
                    {
                        q.push(graph[q.front()][j]);
                    }
                }
            }
            q.pop();
        }
    }
    // return 1;
}

int is_bipartite(int v){
    for(int i = 1; i <= v; i++)
    {
        int size = graph[i].size();
        for(int j = 0; j < size; j++)
        {
            if(visited[i] == visited[graph[i][j]]){
                return 0;
            }
        }
    }
    return 1;
}

int main(){

    int k;
    cin >> k;
    for(int i = 0; i < k; i++)
    {
        int v, e;
        cin >> v >> e;
        int f, t;
        init();
        for(int j = 0; j < e; j++)
        {
            cin >> f >> t;
            graph[f].push_back(t);
            graph[t].push_back(f);
        }
        for(int k = 1; k <= v; k++)
        {
            if(visited[k] == 0){
                bfs(k);
            }
        }
        if(is_bipartite(v)){
            cout << "YES" << endl;
        } else{
            cout << "NO" << endl;
        }
    }

    return 0;
}

• ps
• bfs