이분 그래프 성공

2 초 256 MB 69417 18251 10951 23.507%
문제

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

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

입력

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호 u, v (u ≠ v)가 빈 칸을 사이에 두고 주어진다.

출력

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

제한

2 ≤ K ≤ 5

1 ≤ V ≤ 20,000

1 ≤ E ≤ 200,000
예제 입력 1 복사
2
3 2
1 3
2 3
4 4
1 2
2 3
3 4
4 2
예제 출력 1 복사
YES
NO

BFS나 DFS로 brute-force를 해서 각 노드에 이전 노드와 다른 색깔(0 or 1)을 넣어준 다음

만약 그래프의 간선이 같은 색의 노드를 가리키면, 이분 그래프가 될 수 없다는 것을 이용하면 된다.

문제의 조건을 제대로 보지 못하고 당연히 노드끼리 다 연결되어있는줄 알아서 시작점을 1로 넣고 돌렸는데, 계속틀려서 모든 노드에 대한 탐색을 다 돌리니까 맞았다. 연결되지 않는 경우도 생각해야 된다.

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int K, V, E;
int main(){
    cin>>K;
    while(K--){
        vector<vector<int>>graph(20001);
        bool color[20001]={0};
        int vis[20001] = {0};
        cin>>V>>E;
        for(int i=0; i<E; i++){
            int a, b;
            cin>>a>>b;
            graph[a].push_back(b);
            graph[b].push_back(a);
        }
        // int cur = 1, quit = 0;
        // color[cur] = 0;
        // vis[cur] = 1;
        // //0 -> black, 1 -> red
        // queue<pair<int,int>>q;
        // //first -> node, second -> color
        // q.push({cur, 0});
        int quit = 0;
        for(int i=1; i<=V; i++){
            if(vis[i]) continue;
            color[i] = 0;
            vis[i] = 1;
            queue<pair<int,int>>q;
            q.push({i,0});
            while(!q.empty()){
                auto cur_node = q.front().first;
                auto cur_color = q.front().second;
                q.pop();
                for(auto edge : graph[cur_node]){
                    if(vis[edge]){
                        if(color[edge] == cur_color){
                            //end
                            quit = 1;
                            break;
                        }
                        continue;
                    }
                    vis[edge] = 1;
                    color[edge] = !cur_color;
                    q.push({edge,!cur_color});
                }
                if(quit) break;
            }
            if(quit) break;
        }
        if(!quit){
            for(int i=1; i<=V; i++)
                for(auto edge : graph[i]){
                    if(color[i] == color[edge]) quit=1;
                }
        }
        if(!quit)
            cout<<"YES\n";
        else
            cout<<"NO\n";
            
    }
}