[1707번] 이분 그래프

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 이분 그래프

2. DFS

이 문제는 DFS, BFS 두가지 방법으로 풀 수 있는데 이번 코드에서는 DFS를 이용하여 문제를 해결하였다.

이분 그래프에 대한 기본 문제이며, DFS를 조금 더 깊게 바라봐 주도록 하는 문제인 듯 하다.

소스 코드에 대한 설명은 주석을 통해 모두 적어두었다.

소스 코드 : 

#include<iostream>
#include<vector>
#include<algorithm>
#include<stdio.h>
 
using namespace std;
 
int T, V, E, to, from;
int check[20002];
vector<int> v[20002];
 
/*
    check[pos] = color :: 현재 정점에 색을 부여해준다( + 방문 의미 )
    
    for(int i = 0 ; i < v[pos].size() ; i ++) 
    :: 해당하는 정점에 연결되어있는 모든 정점을 확인

    int next = v[pos][i]; :: 하나씩 정점을 확인 해 나가기 위한 변수

    if(check[next] == color) :: 만약, 이전에 dfs에 의해 check[next]가 이미 
    어떤 색으로 칠해져있었는데 그게 현재 정점 색과 같다면

    if(check[next] == -1 && !dfs(next, !color)) ::
    정점에 처음 왔고, 그 정점부터 시작해서 다시 dfs를 하며,
    색은 반대색을 넣어준다. (이분 그래프의 정의)
*/
bool dfs(int pos, int color)
{
    check[pos] = color;
 
    for (int i = 0; i < v[pos].size(); i++)
    {
        int next = v[pos][i];
        if (check[next] == color) return false;
        if (check[next] == -1 && !dfs(next, !color)) return false;
    }
    return true;
}
 
 
int main()
{
    scanf("%d", &T);
 
    while (T--)
    {
        scanf("%d %d", &V, &E);
 
        // check 배열을 -1로 초기화 해준다
        fill(check, check + 20002, -1);
 
        // 비방향 그래프에서 간선으로 연결된 서로 다른 두 정점을 이어준다.
        for (int i = 0; i < E; i++)
        {
            scanf("%d %d", &to, &from);
            v[to].push_back(from);
            v[from].push_back(to);
        }
 
        int graph = 1; // graph == 1 ? 이분 그래프 : 이분 그래프 아니다.
 
        /*
            for(int i = 1 ; i <= V ; i ++) :: 모든 정점을 순회

            check[i] == -1 :: 아직 방문하지 않은 노드인가?

            dfs(i, 1) :: i번째 정점의 색을 1로해서 시작한다.
        */
 
        for (int i = 1; i <= V; i++)
            if (check[i] == -1 && !dfs(i, 1))
            {
                graph = 0;
                break;
            }
        graph ? printf("YES\n") : printf("NO\n");
 
        for (int i = 0; i <= 20001; i++)
            v[i].clear();
    }
    return 0;
}        
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>