[백준/C++] 1707. 이분그래프

문제

www.acmicpc.net/problem/1707

풀이

 처음에는, 벡터 두개를 만들어서 각 그룹에 노드들을 채워나가는 형식으로 했는데 문제점이 있었다.
그래프가 꼭 두 그룹으로 나뉘지 않는다는 것이었다. 아래 그림의 case2와 같이 독립적인 여러개의 그룹으로 나뉠 수 있었다.

그래서 얌전하게 일반적인 그래프 풀이 방식을 이용하였다.
BFS로 그래프 탐색 후에, 해당 그래프가 이분그래프인지 확인하는 과정을 거쳤다.

간선을 입력받을 때, v1 -> v2만 저장해서 틀렸습니다가 나왔다. 

무방향그래프이기 때문에, v2 -> v1도 저장해야한다! 

 

그리고 BFS를 한 번만 돌리는 것이 아니라, 모든 노드를 방문할 때 까지 여러번 돌려야했다. 

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

#define LEFT 1
#define RIGHT 2

vector<int> graph[200001];
int visited[200001] = {0,};

void BFS(int start){
    queue<int> q;
    q.push(start);
    int flag = LEFT;
    visited[start] = flag; 

    while(!q.empty()){
        int now = q.front();
        q.pop();
        flag = visited[now];
        int nextFlag = LEFT; 
        if (flag == LEFT) nextFlag = RIGHT;
        for (int i=0;i<graph[now].size();i++){
            int next = graph[now][i];

            if (visited[next] == 0){
                q.push(next);
                visited[next] = nextFlag;
            }
        }
    }
}

bool isBipartite(int V) {
    for (int i=0; i<V; i++){
        for (int j=0; j<graph[i].size(); j++){
            if (visited[i] == visited[graph[i][j]])
                return 0;
        }
    }
    return 1;
}
int main(void){
    int T;
    cin >> T;
    for (int t=0;t<T;t++){
        int V,E;
        cin >> V >> E;
        for (int e=0;e<E;e++){
            int a,b;
            cin >> a >> b;
            graph[a-1].push_back(b-1);
            graph[b-1].push_back(a-1); //무방향 그래프 !!!
        }
        // 그래프 탐색 
        // BFS(0);
        for (int i = 0; i < V; i++) { 
            if (visited[i] == 0) { // 해당 노드를 아직 방문하지 않았다면
                BFS(i);
            } 
        }
        // 이분그래프 여부 확인 
        bool result = isBipartite(V);

        //결과 출력 
        if (result) 
            cout << "YES" << endl;
        else   
            cout << "NO" << endl;

        // 초기화 
        for (int i=0;i<V;i++){
            graph[i].clear();
        }
        fill(&visited[0],&visited[200001],0);

    }
}

결과

참고

jdselectron.tistory.com/51