[백준][C++] 1707: 이분 그래프

 

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

1707번: 이분 그래프

 

 

 

 

 

---

- 문제

 

그래프가 주어질 때 해당 그래프가 이분 그래프인지 아닌지 구하는 문제다.

 

 

---

- 해설

 

먼저 이분그래프가 뭔지 알아보자.

 

위의 경우가 이분그래프의 예시다.

 

이분 그래프란 인접한 정점끼리 서로 다른 색으로 칠하여 모든 정점을 두 그룹으로 나누고, 서로 다른 그룹의 정점을 간선으로 연결한 그래프라고 한다.

 

한 마디로 "모든 인접한 정점이 서로 다른 색으로 칠해지면 이분 그래프"이고, 아니면 이분 그래프가 아니다.

 

 

 

문제는, bfs로 풀든 dfs로 풀든 현재 정점에서 이어지는 다른 정점은 해당 정점과 다른 색으로 칠하면 될 것 같다.

 

 

 

 

 

1. 입력을 받으면서 간선을 양방향으로 연결

2. BFS를 통해서 정점에 색을 더해준다.

(첫 색을 빨강으로 하고, 다음 색을 파랑으로, 파랑이면 빨강으로)

3. 색이 잘 칠해졌나 검사하면서, 만약 검사하는 동안 같은 색이 연속으로 나오는 경우가 있으면 NO를, 마지막까지 검사했는데 아무것도 없으면 YES를 출력한다.

 

---

- 풀이

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

#define MAX_SIZE 20000 + 1
#define RED 1
#define BLUE 2

using namespace std;

int K, V, E;
vector<int> graph[MAX_SIZE];
int visited[MAX_SIZE];

void bfs(int start);
bool isBipartiteGraph();

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> K;
    while (K--)
    {
        cin >> V >> E;
        for (int i = 0; i < E; i++)
        {
            int tempOne, tempTwo;
            cin >> tempOne >> tempTwo;
            graph[tempOne].push_back(tempTwo);
            graph[tempTwo].push_back(tempOne);
        }

        for (int i = 1; i <= V; i++)
        {
            if (!visited[i])
            {
                bfs(i);
            }
        }

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

        for (int i = 0; i <= V; i++)
        {
            graph[i].clear();
        }
        memset(visited, 0, sizeof(visited));
    }
    return 0;
}

void bfs(int start)
{
    queue<int> q;
    int color = RED;

    visited[start] = color;
    q.push(start);
    while (!q.empty())
    {
        int now = q.front();
        q.pop();

        if (visited[now] == RED)
        {
            color = BLUE;
        }
        else if (visited[now] == BLUE)
        {
            color = RED;
        }

        int gSize = graph[now].size();
        for (int i = 0; i < gSize; i++)
        {
            int next = graph[now][i];
            if (!visited[next])
            {
                visited[next] = color;
                q.push(next);
            }
        }
    }
}

bool isBipartiteGraph()
{
    for (int i = 0; i <= V; i++)
    {
        int gSize = graph[i].size();
        for (int j = 0; j < gSize; j++)
        {
            int next = graph[i][j];
            if (visited[i] == visited[next])
            {
                return false;
            }
        }
    }
    return true;
}

 

 

---

- 새롭게 알게 된 점

- 이분그래프가 뭔지 알게 되었다.