백준 1707 //

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

 

 

이분 그래프란, 그래프의 정점(노드)을 두 개의 집합으로 나누었을 때, 같은 집합에 속한 정점끼리는 **간선(연결선)**으로 연결되지 않도록 나눌 수 있는 그래프

 

이분 그래프가 되는 조건

1. 그래프의 모든 간선을 따라가며 두 그룹으로 정점을 나눌 수 있어야 함
2. 그래프를 탐색하면서, 각 노드에 색(두 그룹 중 하나)을 칠할 수 있어야 함:
   • 어떤 노드를 한 그룹에 넣었으면, 그 노드와 연결된 모든 노드는 다른 그룹에 있어야 함
3. 탐색 중에 같은 그룹에 있어야 할 노드들이 서로 연결되었다면, 이분 그래프가 아님

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 이분 그래프 판별 함수
bool isBipartite(int V, vector<vector<int>>& graph) 
{
    vector<int> color(V + 1, -1); // -1: 아직 색칠되지 않음, 0과 1: 두 가지 색

    // 모든 정점에 대해 BFS 수행 (여러 연결 요소 처리)
    for (int start = 1; start <= V; start++) 
    {
        if (color[start] == -1) 
        { // 아직 방문하지 않은 정점
            queue<int> q;
            q.push(start);
            color[start] = 0; // 시작 정점에 색 0 할당

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

                for (int neighbor : graph[curr]) 
                {
                    if (color[neighbor] == -1) 
                    {
                        // 인접 정점에 반대 색 칠하기
                        color[neighbor] = 1 - color[curr];
                        q.push(neighbor);
                    } 
                    else if (color[neighbor] == color[curr]) 
                    {
                        // 같은 색이 인접하면 이분 그래프 아님
                        return false;
                    }
                }
            }
        }
    }
    return true;
}

int main() 
{
    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<vector<int>> graph(V + 1);
        for (int i = 0; i < E; i++) 
        {
            int u, v;
            cin >> u >> v;
            graph[u].push_back(v);
            graph[v].push_back(u); // 무방향 그래프
        }

        // 이분 그래프 판별
        if (isBipartite(V, graph)) 
        {
            cout << "YES\n";
        } 
        else 
        {
            cout << "NO\n";
        }
    }

    return 0;
}