[백준 1707번] 이분 그래프 (C++)

문제링크 : https://www.acmicpc.net/problem/1707

1707번: 이분 그래프

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int K, V, E;
vector<int>v[20001];
int visited[20001];
bool flag; //인접색깔 체크용

void dfs(int cur)
{
    if(!visited[cur]) visited[cur] = 1; //우선 색깔 지정

    for(int i=0; i<v[cur].size(); i++)
    {
        int next = v[cur][i];
        if(!visited[next]) //인접한 색깔 반대로
        {
            if(visited[cur]==1) visited[next] = 2; 
            else if(visited[cur]==2) visited[next] = 1;
            dfs(next);
        }
        else
        {
            if(visited[cur]==visited[next]) //인접색깔이 같으면 이분그래프 불가능
            {
                flag = 1;
                return;
            }
        }
    }
}


int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> K;
    while(K--)
    {
        cin >> V >> E;
        flag = 0;
        for(int i=1; i<=V; i++) v[i].clear();
        memset(visited, 0, sizeof(visited));

        for(int i=0; i<E; i++)
        {
            int x, y;
            cin >> x >> y;
            v[x].push_back(y);
            v[y].push_back(x);
        }

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

        cout << (flag==0 ? "YES" : "NO") << "\n";
    }

    return 0;
}

 

dfs를 활용한 문제이다.

우선 양방향 그래프이므로 이에 맞게 입력받은 값을 연결해준다.

 

이후 dfs를 통해 각 정점에 대해 색깔을 지정해준다.

색깔을 지정한 정점을 기준으로 인접 정점들을 살펴주는데, 이분그래프가 되려면 인접 정점의 색깔은 현재 정점의 색깔과 달라야 하므로 다른 색깔을 칠해준다. (1이면 2, 2면 1로)

이렇게 다른 색깔을 칠한 정점을 기준으로 다시 위의 과정을 반복해준다.

 

만약 인접한 정점에 이미 색깔이 존재하고, 해당 색깔이 현재 정점과 동일하다면 이분그래프가 불가능한 것이다.

따라서 이분그래프가 불가능하다는 것을 표시할 bool 변수 flag의 값을 1로 바꾼뒤 (초기값 0) 바로 dfs 탐색을 종료시킨다.

 

이를 방분하지 않은 각 정점에 대해 전부 dfs를 따로 돌려주고 나온 이분그래프 불가능 여부를 표시하는 flag를 기준으로 결과값을 출력해준다.

 

테스크케이스가 여러가지이므로 색깔 및 방문 여부를 확인하는 배열과 정점이 담긴 배열, flag까지 매 탐색마다 초기화해주는 것을 잊으면 안된다.