[BOJ-1707]이분그래프

이분그래프의 정의는 정점을 두 그룹으로 나누었을 때 같은 그룹 정점을 잇는 간선이 존재하지 않는 것.

이분 그래프 - 위키백과, 우리 모두의 백과사전

쾨니그의 정리 는 여기로 연결됩니다. 무한 그래프에 대한 정리에 대해서는 쾨니그 보조정리 문서를 참조하십시오. 쾨니그의 정리 는 여기로 연결...

ko.wikipedia.org

이분 그래프는 각 정점에 색을 두가지만 칠해서 두 그룹으로 나눌 수 있는지 확인을 해주면 된다.

여러가지 방법을 할 수 있을텐데.. 

큐를 사용해서 BFS 탐색을 한다. 

큐에 넣는 조건은 아직 정점에 색을 칠하지 않았을 경우 : 색을 칠하며, 큐에 넣는다.

여기서 색을 칠하는 건 int형으로 값을 0 또는 1로 지정하는 것 색이 칠해져있지 않는 경우 -1

이 경우에 색이 칠해져있는 정점과 인접해져있는 경우

1) 현재 색칠된 정점과 색이 다름 ( == 통과, 이분그래프 여부를 계속 판단해 봐야함. )

2) 현재 색칠된 정점과 색이 같음 ( == 이분그래프가 아님 )

그리고 두 그룹으로 나눌 수 있지만, 

같은 그룹에 있는 정점들이 간선을 타고, 이동할 수 없기도 하기 때문에 그런 경우가 발생하지 않도록 큐가 비어진 경우 색칠하지 않은 정점을 찾아서 다시 큐에 넣는다. 

이 과정을 거쳐서 모든 정점에 색칠이 끝났다면? 이분그래프이다.

아니라면 이분그래프가 아니다.

#include<cstdio>
#include<vector>
#include<queue>
#include<utility>
#define mp(a,b) make_pair(a,b)
using namespace std;
 
typedef vector<int> vi;
typedef pair<int, int> pii;
const int MAX = 22222;
vi G[MAX];
int V[MAX];
queue<pii> Q;
void init(){
    for(int i = 0 ; i < MAX ; i++){
        V[i] = -1;
        G[i].clear();
    }
    while(!Q.empty()){
        Q.pop();
    }
}
 
int main(){
    int T;
    scanf("%d",&T);
    for(int tc = 0 ; tc < T ; tc++){
        bool is_bi_graph = true;
        init();
        int noV, noE;
        int sav_idx = 1; // add code
        scanf("%d%d",&noV, &noE);
 
        for(int i = 0 ; i < noE ; i++){
            int u, v;
            scanf("%d%d", &u, &v);
            G[u].push_back(v);
            G[v].push_back(u);
        } // input 
 
        
        Q.push(mp(1,0)); // start node 1
        V[1] = 0;
        while(!Q.empty()){ // BFS 
            pii here = Q.front(); Q.pop();
            int node_num = here.second;
            int vertex = here.first;
            if(!is_bi_graph){
                break;
            }
            for(int i = 0 ; i < G[vertex].size() ; i++){
                int there = G[vertex][i];
                if(V[there]==-1){
                    V[there] = ((node_num+1) % 2);
                    Q.push(mp(there,V[there]));
                }else if(V[there] == node_num){
                    is_bi_graph = false;
                }
            }
            if(Q.empty()){ // Q가 빈 경우, 모두 색칠하였는지 확인
                for(int i = sav_idx ; i <= noV ; i++){
                    if(V[i]==-1){ // 색이 칠해지지 않은 경우.
                        sav_idx = i+1;
                        V[i]=0;                        
                        Q.push(mp(i,V[i]));
                        break;
                    }
                }
            }//add code 60% WA
        }
        printf("%s\n",(is_bi_graph?"YES":"NO"));
    }
    return 0;
}