[c++] BOJ 1707 :: 이분 그래프

난이도 : 골드 4

걸린 시간 : 오래 걸림

 

문제

이분 그래프 문제 보러가기

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

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

 

풀이

• bfs로 순회하면서 두 가지 색으로 칠하기 (1, -1)
• 이미 칠해진 곳이 다른 색으로 칠해져야 한다면 이분 그래프가 아님

 

코드

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

using namespace std;
vector<int> vec[20001];

bool bfs(vector<int>& check, int start) {
    queue<int> que;
    que.push(start);
    while (!que.empty()) {
        int tmp = que.front(); que.pop();
        int comp = check[tmp]; // 비교 값
        for (int i = 0; i < vec[tmp].size(); i++) {
            int tmp2 = vec[tmp][i];
            if (check[tmp2] == comp) {
                // 이분 그래프 x
                return false;
            }
            if (check[tmp2] != 0)
                // 이미 들른 곳
                continue;
            check[tmp2] = comp * (-1);
            que.push(tmp2);
        }
    }
    return true;
}

int main() {
    // r,b 색칠하기
    // 그래프 표현 ( 연결 리스트 )
    // bfs로 돌면서 색 겹치면 no

    int K; cin >> K;
    vector<string> answer;

    while (K--) {
        int V, E; cin >> V >> E;
        for (int i = 1; i <= V; i++) {
            vec[i].clear();
        }
        for (int i = 0; i < E; i++) {
            int s, e; cin >> s >> e;
            vec[s].push_back(e);
            vec[e].push_back(s);
        }

        vector<int> check(V + 1, 0);
        int flag = false;
        for (int i = 1; i <= V; i++) {
            if (check[i] != 0) // 이미 들른 곳은 다시 보지 x
                continue;
            else
                check[i] = 1; // 들르지 않은 곳은 1로 시작
            if (!bfs(check, i)) {
                answer.push_back("NO");
                flag = true;
                break;
            }
        }
        if (!flag)
            answer.push_back("YES");
    }
    for (int i = 0; i < answer.size(); i++) {
        cout << answer[i] << '\n';
    }
}

 

결과