[백준] 1707번 이분 그래프

문제

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

풀이과정

주어진 그래프가 이분 그래프인지 아닌지 출력하는 문제이다.
먼저 이분 그래프란 무엇인지 찾아보니 모든 노드를 빨강색 혹은 파랑색으로 칠하는데 같은 색을 가진 노드는 서로 인접하지 않는 위치에 존재하는 그래프이다.

이분 그래프인지 아닌지 판별하는 방법은 dfs나 bfs로 그래프를 탐색하며 노드를 색칠하고 색칠되어 있는 노드를 방문할 경우 인접한 노드와 같은 색깔이면 이분 그래프가 아니라고 판별할 수 있다.

소스코드

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

using namespace std;

vector<int> a[20001];
int color[20001];

void dfs(int node, int c) 
{
    color[node] = c;
    for (int i = 0; i<a[node].size(); i++) 
    {
        int next = a[node][i];
        if (color[next] == 0) 
        {
            dfs(next, 3 - c);
        }
    }
}

int main() 
{
    cin.sync_with_stdio(false);

    int T;

    cin >> T;

    while (T--) 
    {
        int n, m;
        cin >> n >> m;
        for (int i = 1; i <= n; i++) 
        {
            a[i].clear();
            color[i] = 0;
        }
        for (int i = 0; i<m; i++) 
        {
            int u, v;
            cin >> u >> v;
            a[u].push_back(v); a[v].push_back(u);
        }
        for (int i = 1; i <= n; i++) 
        {
            if (color[i] == 0) 
            {
                dfs(i, 1);
            }
        }
        bool ok = true;
        for (int i = 1; i <= n; i++) 
        {
            for (int k = 0; k<a[i].size(); k++) 
            {
                int j = a[i][k];
                if (color[i] == color[j]) 
                {
                    ok = false;
                }
            }
        }

        if (ok) cout << "YES\n";
        else cout << "NO\n";
    }

    return 0;
}