백준 1707번 C++ 이분 그래프

이분 그래프

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

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

푸는 법

이분 그래프인지 확인하는 법

알고리즘 검색하다 보면 꼭 나오는 이 분의 블로그를 보고 그냥 이대로만 하면 맞을 수 있다.

주의할 점은 테스트 케이스를 실행할 때마다 그래프와 체크를 초기화해주는 것이다.

나는 DFS로 풀었고, 만약 start의 색깔과 next의 색깔이 이미 존재하고(둘다 방문했고) 색깔이 같으면 재귀문을 빠져나와 answer이 NO가 되도록 했다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#define red 1
#define blue 2
using namespace std;
string answer;
void dfs(vector<int> graph[], int check[], int start) {
    for(int i=0; i<graph[start].size(); i++) {
        int next=graph[start][i];
        if(check[start]!=0&&check[next]!=0&&check[start]==check[next]) {
            answer="NO";
            break;
        }
        if(check[next]==0) {
            check[next]=red;
            if(check[start]==red){
                check[next]=blue;
            }
            dfs(graph, check, next);
        }
    }
}
int main() {
    int K;
    scanf("%d", &K);
    while(K>0) {
        int V, E;
        scanf("%d %d", &V, &E);
        vector<int> graph[20001];
        int check[20001]={0,};
        for(int i=0; i<E; i++) {
            int a, b;
            scanf("%d %d", &a, &b);
            graph[a].push_back(b);
            graph[b].push_back(a);
        }
        answer="YES";
        for(int i=1; i<=V; i++) {
            if(check[i]==0) {
                check[i]=red;
                dfs(graph, check, i);
            }
        }
        cout<<answer<<"\n";
        K--;
    }
    return 0;
}

메모리가 조금 깔끔하지 못하게 나온 것 같긴 한데 일단 맞았다.

정답률 21%은 아마 초기화를 하지 않은 코드에서 나온 것 같다.