백준 1707: 이분 그래프

문제

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

이분 그래프란?

☞모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을포함하도록 색칠 할수 있는 그래프.

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

▼ 이분 그래프의 예시

해당 문제는 주어지는 그래프가 이분 그래프인지를 확인하는 문제입니다.

예시를 보면 "하나의 정점에서 연결된 다른 정점들의 색상은 다르다" 인 것을 확인 할 수 있습니다.

이분 그래프의 특징을 이용하여 문제를 푸는 것이 핵심입니다.

DFS 혹은 BFS로 그래프를 탐색을 하여 이미 방문했던 정점을 확인할 때, 만약 자신과 같은 색상을 가지고 있다면 

해당 그래프는 이분 그래프가 아닙니다. 

코드

#include <iostream>
#include <vector>
 
using namespace std;
 
vector<int> G[20001];
int color[20001];      //1일때는 빨강, 2일때는 파랑, 0일때는 접근X
 
void DFS(int node, int c){
    color[node] = c;
    for(int i=0; i<G[node].size(); i++){
        int next = G[node][i];
        if(color[next]==0){
            DFS(next, 3-c); //빨강 다음에는 파랑이여야하고 파랑 다음은 빨강이여야 함.
                            //따락서 3-1 = 2, 3-2 = 1
        }
    }
}
int main(){
    int t;
    cin >> t;
    while (t--) {
        int n,m;
        cin >> n >> m;
        for(int i=1; i<=n; i++){
            G[i].clear();
            color[i]=0;
        }
        for(int i=0; i<m; i++){
            int u,v;
            cin >> u >> v;
            G[u].push_back(v);
            G[v].push_back(u);
        }
        for(int i=1; i<=n; i++){
            if(color[i]==0){
                DFS(i, 1);
            }
        }
        bool isBin=true;
        for(int i=1; i<=n; i++){
            for(int j=0; j<G[i].size(); j++){
                int k = G[i][j];
                if(color[i]==color[k])
                    isBin=false;
            }
        }
        if(isBin)
            cout <<"YES"<<"\n";
        else
            cout <<"NO"<<"\n";
    }
    return 0;
}