[BOJ] 1707 이분 그래프

 

이분 그래프를 먼저 알고 이해하고 있어야 풀 수 있는 문제였다. bfs로만 풀어봤는데

우선 이분그래프를 다시 설명해보자면 서로 연결된 그래프가 있으면 그걸 두 집합으로 나누려고 한다. 이걸 색깔로 구분하는 것이다. 자신이랑 연결된 노드들은 다른 색으로 칠한다. 그게 불가능하다면 이분 그래프가 되지 못한다. 자신과 연결된 노드가 같은 집합에 속하는 것이 되기때문이다.

 

테스트케이스

11 3 1 2 3 3 2 1 3 2 3 4 4 1 2 2 3 3 4 4 2 3 2 2 1 3 2 4 4 2 1 3 2 4 3 4 1 5 2 1 5 1 2 5 2 1 2 2 5 4 3 1 2 4 3 2 3 4 4 2 3 1 4 3 4 1 2 3 3 1 2 2 3 3 1 2 1 1 2 예제 출력1 YES YES NO YES YES YES YES YES YES NO YES

[알고리즘] 이분 그래프(Bipartite Graph)란 - Heee's Development Blog

 

 

bool BFS(int start){

    queue<int> q;
    q.push(start);
    while(!q.empty()){

        int cur = q.front();
        visit[cur] = true;
        q.pop();

        for( int i =0 ; i < G[cur].size() ; i++ ){
            int next = G[cur].at(i);
            if( (color[cur] == color[next] ) && visit[next] ){
                return false;
            }else if ( !visit[next] ){
                color[next] = 1- color[cur];
                q.push(next);

            }
        }
    }

    return true;

}

bool BFS2(int start){

    queue<int> q;
    q.push(start);
    while(!q.empty()){

        int cur = q.front();
        q.pop();

        for( int i =0 ; i < G[cur].size() ; i++ ){
            int next = G[cur].at(i);
            if( (color[cur] == color[next] ) && color[next]!=-1 ){
                return false;
            }else if ( color[next]==-1 ){
                color[next] = 1- color[cur];
                q.push(next);

            }
        }
    }

    return true;

}