[백준/C,C++] 1707번: 이분 그래프

www.acmicpc.net/problem/1707

1707번: 이분 그래프

풀이

이분 그래프라 함은 모든 꼭짓점을 빨강과 파랑으로 칠하되,

 

모든 변이 빨강과 파랑을 포함하도록 색칠할 수 있는 그래프를 말합니다(출처 : 위키백과).

 

즉 같은 레벨(깊이)의 정점은 모두 같은 색으로 칠할 수 있어야 합니다.

 

너비 우선 탐색을 하며 방문하지 않은 정점이라면 이전 레벨의 노드와 반대의 색을 칠하고

 

방문한 정점이라면 이전 레벨의 노드와 색이 반대인지 체크한 후에 반대가 아니라면

 

이분 그래프가 아님을 알 수 있습니다.

 

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

#define visited first
#define color second

using namespace std;

const int MAX = 20001;

pair<bool, bool> p[MAX];

bool BFS(const vector<int>* graph, int num)
{
    queue<int> q;
    q.push(num);
    p[num].visited = true;

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        size_t sz = graph[node].size();
        for (size_t i = 0; i < sz; i++) {
            int next = graph[node][i];
            if (p[next].visited) {
                if (p[next].color == p[node].color) return false;
            }
            else {
                q.push(next);
                p[next].visited = true;
                p[next].color = !p[node].color;
            }
        }
    }

    return true;
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int k; cin >> k;

    while (k--) {
        int v, e; cin >> v >> e;
        vector<int> graph[MAX];

        while (e--) {
            int a, b; cin >> a >> b;
            graph[a].push_back(b);
            graph[b].push_back(a);
        }

        bool ret = true;
        for (int i = 1; i <= v; i++) {
            if (!p[i].visited && ret) ret = BFS(graph, i);
        }
        if (ret) cout << "YES\n";
        else cout << "NO\n";

        fill(p, p + MAX, pair(false, false));
    }

    return 0;
}

반례

Input

3
3 2
1 2
2 3
3 3
1 2
2 3
3 1
4 3
1 4
4 2
4 3

Output

YES

NO
YES