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

www.acmicpc.net/problem/1707

1707번: 이분 그래프



이 문제는 두 개의 정점이 주어졌을 때, 

두개의 정점은 인접하지 못하도록 표시 후,

이분 그래프가 맞는지 판별하는 문제입니다.

 

BFS, DFS 둘 중 아무거나 사용하면 됩니다.

 

이분 그래프 알고리즘의 핵심은, 두 개의 정점이 인접하지 못하도록, 2 가지 색깔로 칠해주는 것입니다.

 

처음 노드를 선택했을 때 1, 1로 칠해진 노드안에 있는 다음 노드를 선택 했을 때 2, 그리고 2노드안에 있는 다음 노드를 선택했을 때 1,

이런식으로 계속 번갈아 가면서 칠해주면 됩니다.

 

구현하기 전에, 간선을 양방향으로 만들어주는 것이 중요합니다. 

왜냐하면, 왼쪽 오른쪽으로 나눴을 때 같은 숫자가 왼쪽 오른쪽 둘다 존재하면 안되기 때문입니다.

 

색칠하는 것에 한마디로 정리하자면, 색을 안칠했을 땐 0, 하나의 색깔 1, 또 다른 하나의 색깔 2로 구분해서,

색은 안칠했을 때만 노드에 색을 칠해주는 형식으로 구현하시면 되겠습니다.

이미지 출처: https://en.wikipedia.org/wiki/Complete_bipartite_graph

 

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;


const int MAX = 20001;
vector<int> vertex[MAX];
int color[MAX]; // 0은 아직, 1,2는 색깔구별


int v, e;

void dfs(int k, int coloring){
    
    color[k] = coloring;

    for (int i = 0; i < vertex[k].size(); i++){
        int next = vertex[k][i];

        if (color[next] == 0){
            dfs(next, 3 - coloring);
        }
    }

}
bool isBigraph(){
    for (int i = 1; i <= v; i++){
        for (int j = 0; j < vertex[i].size(); j++){
            int next = vertex[i][j];
            if (color[i] == color[next]) return false;
        }
    }

    return true;

}
void solution(){
    int t;
    cin >> t;

    while(t--){

        memset(color, 0, sizeof(color));
        for (int i = 0; i < MAX; i++) vertex[i].clear();

        
        cin >> v >> e;

        for (int i = 0; i < e; i++){
            int a, b;
            cin >> a >> b;

            vertex[a].push_back(b);
            vertex[b].push_back(a);
        }

        for (int i = 1; i <= v; i++){
            if (color[i] == 0)dfs(i, 1);
        }

        if (isBigraph()) cout << "YES" << '\n';
        else cout << "NO" << '\n';


    }
}
int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solution();

    return 0;
}