BOJ 1707번 이분 그래프

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

GitHub : https://github.com/junho0956/Algorithm/blob/master/1707/1707/%EC%86%8C%EC%8A%A4.cpp

 

이분 그래프는 그래프를 정확히 2종류의 정점 집합으로 나눌 수 있는가에 대한 문제이다.

집합을 나누는 기준은 임의의 정점과 연결된 정점이 서로 다른 관계임을 표현하면 된다.

** 트리가 아닌 그래프를 표현할 때는 방향이 없으므로 서로 이어주도록 하자.. 이거 때문에 처음에 틀렸다 ㅜㅜ**

** 이분 그래프는 모든 정점이 반드시 연결되어 있지 않을 수도 있다 ==> 연결요소가 몆개인지 알 수 없다 **

** 매 테스트케이스마다 초기화를 잘해줘야 한다 **

 

임의의 첫 출발점을 0 이라는 관계를 주었으면 이 정점과 연결된 모든 정점은 반드시

0이 아닌 다른 관계(ex:1) 를 주어야 한다.

이후 임의의 정점에 연결된 정점을 확인할 때 자신과 같은 관계가 있다면 이분 그래프가 될 수 없다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
 
queue<int> q;
vector<int> v[20001];
bool graph[20001];
bool visit[20001];
int K, vertex, edge, s, e;
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    cin >> K;
    while (K--) {
        cin >> vertex >> edge;
 
        memset(graph, -1, sizeof(graph));
        memset(visit, 0, sizeof(visit));
        for (int i = 1; i <= vertex; i++) v[i].clear();
 
        for (int i = 0; i < edge; i++) {
            cin >> s >> e;
            v[s].push_back(e);
            v[e].push_back(s);
        }
 
        bool check = true;
        
        int cnt = vertex, start;
        while (cnt) {
            for (int i = 1; i <= vertex; i++) {
                if (!visit[i]) {
                    start = i;
                    break;
                }
            }
            q.push(start);
            graph[start] = 0;
 
            while (!q.empty()) {
                int cur = q.front();
                int now = graph[cur];
                q.pop();
 
                if (visit[cur]) continue;
                visit[cur] = 1;
                cnt--;
 
                for (int i = 0; i < v[cur].size(); i++) {
                    if (graph[v[cur][i]] == now) {
                        check = false;
                        break;
                    }
                    if (!visit[v[cur][i]]) {
                        q.push(v[cur][i]);
                        if (now == 0) graph[v[cur][i]] = 1;
                        else graph[v[cur][i]] = 0;
                    }
                }
                if (!check) while (!q.empty()) q.pop();
            }
            if (!check) break;
        }
 
        if (check) cout << "YES\n";
        else cout << "NO\n";
    }
 
    return 0;
}