BOJ : 1707 이분 그래프

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

github : https://github.com/JEONG-SEUNGWOOK/BOJ/blob/master/1707.cpp

한 노드가 1 또는 0의 값을 가지고 있다고 하면 다음 노드는 반대 값을 가지고 있는 것이 이분 그래프라고 생각하면 된다.

1-0-1-0

|

0-1        뭐 이런 식으로..?

start 노드를 기준으로 DFS를 이용해 다음 노드를 탐색하며 기준 노드와 다음 노드가 다른 값을 가지는지 검사한다.

#include <vector>
#include <cstdio>
using namespace std;

vector<int> G[20001];
int value[20001];
int V, E;
int flag = 1;
bool dfs(int start,int f){
    
    value[start]=f;
    for(int i=0; i<G[start].size(); i++){
        int v = G[start][i];
        if(value[v]==0 && !dfs(v,-f)) {
            return false;
        }
        if(value[v]==f){
            return false;
        }
    }
    return true;
}
void process(){
    
    for(int i=0; i<V; i++){
        if(value[i]==0 && !dfs(i, 1)){
            printf("NO\n");
            return;
            
            
        }
    }
    printf("YES\n");
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d %d",&V, &E);
        for(int i=0; i<V; ++i){
            G[i].clear();
            value[i]=0;
        }
        while(E--){
            int a,b;
            scanf("%d %d",&a, &b);
            a--;b--;
            G[a].push_back(b);
            G[b].push_back(a);
        }
        if(V == 1){
            printf("NO\n");
            continue;
        }
        else process();
    }
    return 0;
}