이분 그래프와 판별법

이분 그래프란?

이분 그래프는 노드가 두 개의 그룹으로 분리되어 있는 그래프를 말한다.

인접한 정점끼 서로 다른 색으로 색칠하여 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프이다.

 

 

철수부터 색을 칠하면 인접한 정점은 철수와 반대되는 색으로 칠한다

철수와 인접한 수학은 주황색으로 칠해진다.

 

다시 수학과 인접한 영희를 수학과 반대되는 파란색으로 칠하고 영희와 인접한 국어를

주황색으로, 국어와 인접한 세희를 파란색으로..쭉쭉 칠하면

 

모든 정점을 두 가지의 각기 다른 색으로 칠할 수 있다.이러한 그래프를 이분 그래프라고 부른다.

모든 정점을 방문하며 간선을 검사하기 때문에 시간 복잡도는 O(V+E)로 그래프 탐색 알고리즘과 같다.

이분 그래프의 판별법

서로 인접한 정점이 같은 색이면 이분 그래프가 아니다!

 

-그래프 탐색을 해서 정점을 방문할 떄마다 2가지 색 중 하나를 고른다.

-다음 정점을 방문하면서 자신과 인접한 정점은 자신과 다른 색으로 칠한다

-자신과 인접한 정점의 색이 자신과 동일하면 이분그래프가 아니다.

 

그래프가 비연결 그래프일 떄도 이를 확인할 필요가 있다.

비연결 그래프는 그래프 내의 어떤 두 정점도 서로 경로가 존재하지 않는 것을 말한다

 

 

--1707번

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>

using namespace std;

int main() {
    int t;
    cin >> t;

    while (t--) {
        vector<int> graph[20001];
        int color[20001];
        int V, E;
        cin >> V >> E;

        memset(color, -1, sizeof(color));

        for (int i = 0; i < E; i++) {
            int firstNode, secondNode;
            cin >> firstNode >> secondNode;
            graph[firstNode].push_back(secondNode);
            graph[secondNode].push_back(firstNode);
        }
        bool flag = false;
        // 0과 1 색상
        for (int i = 1; i <= V; i++) {
            if (color[i] == -1) {
                queue<int> q;
                q.push(i);
                color[i] = 0;
                

                while (!q.empty()) {
                    int cur = q.front();
                    q.pop();

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

                        if (color[next] == -1) {
                            if (color[cur] == 0) {
                                color[next] = 1;
                            } else if (color[cur] == 1) {
                                color[next] = 0;
                            }
                            q.push(next);
                        } else {
                            if (color[cur] == color[next]) {
                                flag = true;
                            }
                        }
                    }
                }
            }
        }
        if (flag) {
            cout <<  "NO" << '\n';
        } 
        else {
            cout << "YES" << '\n';
        }
    }
    return 0;
}