백준 1707 - 이분 그래프

문제

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

1707번: 이분 그래프

 

풀이

이분 그래프 설명:

https://ko.wikipedia.org/wiki/%EC%9D%B4%EB%B6%84_%EA%B7%B8%EB%9E%98%ED%94%84

이분 그래프 - 위키백과, 우리 모두의 백과사전

 

vector의 배열을 이용하면 그래프를 표현할 수 있다. 2차원 배열로 했을 때 메모리 초과가 발생했다.

 

1. dfs 탐색을 하면서 정점들을 RED, BLUE 로 나눈다.

2. i = 1 부터 i = N 까지 모든 정점에서 현재 i 와 연결된 정점의 색깔을 비교한다. 

3. 현재 i와 연결된 정점의 색깔이 같으면 NO를 출력한다.

4. 색깔이 겹치지 않으면 YES를 출력한다.

 

코드

#include <iostream>
#include <vector>
using namespace std;
 
vector<int> graph[20001];
int K, V, E;
int x, y;
int visit[20001]; // 방문 안하면 0, RED: 1, BLUE: 2
 
void dfs(int v, int color)
{
    visit[v] = color; // RED:1, BLUE: 2
 
    for (int i = 0; i < graph[v].size(); i++)
    {
        int next = graph[v][i];
        if (!visit[next]) dfs(next, 3 - color);
    }
}
 
bool search()
{
    for (int i = 1; i <= V; i++)
    {
        for (int j = 0; j < graph[i].size(); j++)
        {
            int next = graph[i][j];
            if (visit[i] == visit[next]) return false;
        }
    }
    return true;
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> K;
 
    while (K--)
    {
        cin >> V >> E;
        for (int i = 1; i <= V; i++)
        {
            visit[i] = 0;
            graph[i].clear();
        }
 
        while (E--)
        {
            cin >> x >> y;
            graph[x].push_back(y);
            graph[y].push_back(x);
        }
 
        for (int i = 1; i <= V; i++)
            if (!visit[i]) dfs(i, 1);
        
        cout << (search() ? "YES" : "NO") << '\n';
    }
 
    return 0;
}