Baekjoon-1707)이분 그래프

백준 사이트 URL : https://www.acmicpc.net/problem/1707

문제 분석

입력 : 테스트크기 T, 정점의 개수 V, 간선의 개수 E, E개의 연결정보

출력 : 그래프가 이분 그래프를 이루는지에 대한 여부

제한 : 시간제한 2초, 메모리제한 128MB

아이디어 : 이분그래프가 맞는지 확인해주면된다.
            : http://sanghoon9939.tistory.com/33 에서 확인 가능하다.
            : 간단하게 visit 처리를 색으로 해준후 이미 visit된 정점을 확인할때 자신과 같은 색이면, NO처리를 해준다.
 

소스코드

#include<iostream>
#include<string>
#include<vector>
using namespace std;
 
enum color{RED, BLUE};
 
vector <int> map[20001];
int vertex[20001];
string res = "YES";
int v, e;
int cnt = 0;
 
void dfs(int v_, int color) {
    vertex[v_] = color;
    cnt++;
    if (cnt == v)
        return;
    
    for (int i = 0; i < map[v_].size(); i++) {
        if (vertex[map[v_][i]] == -1)
            dfs(map[v_][i], (color + 1) % 2);
        if (vertex[map[v_][i]] == color) {
            res = "NO";
            return;
        }
    }
 
    return;
}
 
int main() {
    int t;
    cin >> t;
 
    for (int i = 0; i < t; i++) {
        res = "YES";
        for (int j = 0; j < 20001; j++) {
            vertex[j] = -1;
            map[j].clear();
        }
        cin >> v >> e;
 
        for (int j = 0; j < e; j++) {
            int v_1, v_2;
            cin >> v_1 >> v_2;
 
            map[v_1].push_back(v_2);
            map[v_2].push_back(v_1);
        }
 
        for (int j = 1; j <= v; j++) {
            if (vertex[j] == -1)
                dfs(j,RED);
        }
        cout << res << endl;
 
    }
    
 
    return 0;
}