그래프_백준_이분 그래프_1707

Bipartite Graph

그래프를 아래의 그래프와 같이 나눌 수 있으면 이분 그래프라고 한다.

즉, A에 포함되어 있는 정점끼리 연결된 간선이 없고 B에 포함되어 있는 정점끼리 연결된 간선이 없다.

따라서 간선의 양 끝점이 다른지 체크 하면 된다.

    

- 먼저 간선의 양 끝점의 위치를 check 배열에 표시를 하고, check 배열을 통해 양 끝점의 위치가 다른지를 확인한다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
 
vector <int> value[20001];
int check[20001]; // value means that '0' is not to visit, '1' is red location, '2' is blue location
 
void dfs(int node, int color) {
    check[node] = color;
 
    for (int i = 0; i < value[node].size(); i++) {
        int next = value[node][i];
        if (check[next] == 0) {
            dfs(next, 3 - color); // Change colors in turn.
        }
    }
}
 
int main() {
    int count;
    cin >> count;
    for (int a = 0; a < count; a++) {
        int vertex, edge;
        cin >> vertex >> edge;
 
        int u, v;
 
        memset(value, 0, sizeof(value));
        memset(check, 0, sizeof(check));
        //Initialize
 
        for (int i = 0; i < edge; i++) {
            cin >> u >> v;
            value[u].push_back(v);
            value[v].push_back(u);
        }//Undirected Graph
 
        for (int i = 1; i <= vertex; i++) {
            if (check[i] == 0) {
                dfs(i, 1);
            }
        }//Identify places.
 
        bool select = true;
        for (int i = 1; i <= vertex; i++) {
            for (int j = 0; j < value[i].size(); j++) {
                int tmp = value[i][j];
                if (check[i] == check[tmp]) {
                    select = false;
                }
            }
        }// Compare the ends of the edge.
 
        if (select) cout << "YES" << endl;
        else cout << "NO" << endl;
 
    }
 
}