[C/C++] 백준 #1707 이분 그래프(그래프 이론)

이번 문제는 그래프가 주어졌을 때, 정점들을 두개의 그룹을 나누었을 때, 인접한 정점들이 같은 그룹에 없도록 만들 수 있다면 이분 그래프가 됩니다.

 

 

이 문제를 풀기 위해서는

1) 현재 그룹에 참여하지 않은 임의의 정점을 고른다.

2) 해당 정점을 그룹 1에 넣는다.  그런 후 해당 정점을 큐에 넣는다.

3) 큐에서 정점을 하나 가져온다.  큐가 비어 있다면 1)번으로 돌아간다.

3) 해당 정점과 인접한 정점들 중에 해당 정점과 같은 그룹에 속해 있으면 이분그래프를 만들 수 없다.

     그렇지 않고 다른 그룹에 이미 들어 있다면, 해당 정점은 무시한다.

     그룹에 속해 있지 않은 정점이라면 다른 그룹에 넣고, 큐에 넣는다.

4) 3)번으로 돌아간다.

 

알고리즘 자체는 쉬운데, 제가 작성한 소스는 현재 그룹에 참여하지 않은 임의의 정점을 고르는데 있어서 비효율적인 방법을 택했네요.  집합을 사용하거나 했다면, 해당 부분을 빠르게 처리할 수 있었을텐데요.  아쉬운 지점이지만, 한번만에 통과해서 그냥 놔두었습니다.

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//-------------------------------------------------------------------------
//    baekjoon #1707
//        - by Aubrey Choi
//        - created at 2019-10-15
//-------------------------------------------------------------------------
#include <stdio.h>
#include <unordered_set>
#include <queue>

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n, m, a, b, bip=1;
        scanf("%d%d",&n,&m);
        std::unordered_set<int> adj[n];
        std::queue<int> q;
        char v[n]; for(int i=0;i<n;i++) v[i]=0;
        while(m--)
        {
            scanf("%d%d",&a,&b); a--, b--;
            adj[a].insert(b);
            adj[b].insert(a);
        }
        for(a=0;bip&&a<n;)
        {
            for(b=0;b<n;b++) if(v[b]==0) break;
            q.push(b); v[b]=1; a++;
            while(!q.empty() && bip)
            {
                int s=q.front(), p=v[s]; q.pop();
                for(auto k : adj[s])
                {
                    if(v[k]&p) { bip=0; break; }
                    if(v[k]) continue;
                    q.push(k); v[k]=p^3; a++;
                }
            }
        }
        puts(bip?"YES":"NO");
    }
}