[1707] 이분 그래프

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

정점과 간선들이 주어졌을 때

이 그래프를 이분 그래프로 나눌 수 있냐 없냐 물어보는 문제이다.

이분 그래프는 그래프를 정점 기준으로 두 집합으로 나누었을 때 그 집합 안에서

정점들 간의 간선이 존재하지 않는 그래프를 뜻한다.

그럼 어떻게 이 문제를 해결할까?

간단하게 DFS를 돌면서 내가 현재 보고있는 정점과 그 정점의 인접한 정점들을 구분지어주면 된다.

난 0과 1를 사용해서 구분지었는데 편하게 색깔이라고 생각하면 될 것 같다.

만약 현재 정점이 0번 색이라면 방문하지 않았던 인접한 정점들은 1번 색으로 칠해준다.

만약 인접한 정점이 이미 방문했던 정점이라면 색을 확인해보고 만약 나랑 같은 색을 가지고 있다면

이 그래프는 이분 그래프가 될 수가 없다고 판단하면 된다. (색을 기준으로 집합을 나눌건데 그 안에 간선이 존재한다는 뜻이므로)

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
bool visit[20200], bipartite[20200], endflag;
void dfs(int pos, bool flag, vector<vector<int> > &v){
    if(endflag) return;
 
    visit[pos] = 1;
    bipartite[pos] = flag;
    for(int i=0; i<(int)v[pos].size(); i++){
        int next = v[pos][i];
        if(!visit[next]){
            dfs(next, !flag, v);
        }else{
            if(bipartite[next] == flag) {
                endflag = 1;
            }
        }
    }
}
int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        int n, m;
        scanf("%d %d", &n, &m);
        vector<vector<int> > vt;
        vt.resize(n+1);
        for(int i=0; i<m; i++){
            int u, v;
            scanf("%d %d", &u, &v);
            vt[u].push_back(v);
            vt[v].push_back(u);
        }
        memset(visit, 0, sizeof(visit));
        memset(bipartite, 0, sizeof(bipartite));
        for(int i=1; i<=n; i++){
            endflag = 0;
            if(visit[i]==0){
                dfs(i, 0, vt);
                if(endflag){
                    puts("NO");
                    break;
                }
            }
        }
        if(endflag) continue;
        puts("YES");
    }
    return 0;
}