[BFS/DFS] 이분 그래프(1707)

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

1707번: 이분 그래프

 

1. 문제 개요

 

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

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

 

 

2. 입출력

 

 

 

3. 문제 풀이

 

BFS 또는 DFS를 이용하되 그래프를 색칠해나가면서 이분 그래프인지 확인하는 부분을 넣어주면 되는 문제이다.

연결그래프라는 조건이 없으니 모든 정점에 대해 탐색할 수 있도록 한다. 

또한 테스트케이스가 여러개이므로 배열과 벡터를 초기화해주어야한다.

 

BFS

• 처음 방문하는 정점을 1로 색칠해준다.
• 방문하는 정점의 인접한 정점들을 -1로 색칠해준다.
• 그 다음 레벨의 정점들의 인접한 정점들을 반대 부호로 색칠해준다.

 

 

4. 전체 코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

const int MAX = 20002;

int list[MAX];
int V, E;
vector<int> v[MAX];

bool BFS(int index) {
    queue<int> q;
    q.push(index);
    list[index] = 1;
    while(!q.empty()) {
        int current = q.front();
        q.pop();
        for(int i=0;i<v[current].size();i++) {
            int next = v[current][i];
            if(list[next]==list[current])
                return false;
            if(list[next]==0) {
                list[next] = list[current]*-1;
                q.push(next);
            }
        }
    }
    return true;
}

int main (void) {
    int K;
    cin >> K;
    
    for(int i=0;i<K;i++){
        string isBipartite = "YES";
        cin >> V >> E;
        for(int j=0;j<E;j++){
            int e1,e2;
            cin >> e1 >> e2;
            v[e1].push_back(e2);
            v[e2].push_back(e1);
        }
        for(int k=1;k<=V;k++){
            if(list[k]==0)
                if(!BFS(k)){
                    isBipartite = "NO";
                    break;
                }
        }
        cout << isBipartite << "\n";
        memset(list, 0, sizeof(list));
        for(int i=1;i<=V;i++) v[i].clear();
    }
}