[C++/백준] 1707번: 이분 그래프

문제 링크

1707번: 이분 그래프

 

풀이

이분 그래프란 두 집합이 있을 때 하나의 정점은 하나의 집합에 속해야 하는데, 인접한 정점은 같은 집합에 포함되면 안된다는 그래프이다. 주의할 점은 시작 정점에서 연결되지 않은 정점도 체크를 해줘야한다는 것.

1. 테스트 케이스의 수만큼 입력을 받고, 각 테스트 케이스마다 인접 리스트를 초기화해준다. 무방향 그래프이기 때문에 입력 받은 두 정점을 양쪽에 다 넣어줘야한다.
2. BFS를 시작할텐데 정점을 돌며 visit이 0인 (방문하지 않은 정점)일 경우 BFS를 시작해준다. 연결되지 않은 정점 체크를 위함이다.
   1. 다른 BFS문제와 같이 queue를 이용하는데, 현재 정점을 q에 넣고, visit도 집합 1로 설정해주며 q가 빌 때까지 반복한다.
   2. 다음 정점의 visit이 0이 아닐 경우 이미 방문했었기 때문에 현재 정점과 다음 정점의 집합을 비교한다. visit
   3. 같을 경우, 인접한 정점이 한 집합에 있다는 뜻이 되므로 return false한다.
   4. 다음 정점을 방문하지 않았다면, 현재 정점이 집합 1에 있으면 2에, 2에 있으면 1에 넣어준다.
   5. return 되지 않고 정상적으로 끝났다면 이분 그래프라는 뜻이므로 return true한다.
3. 그렇게 모든 정점을 돌았을 때, 하나라도 NO가 나오면 NO이므로 &연산으로 답을 구한 뒤 출력한다.

 

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

bool BFS(vector<vector<int>>& arr, vector<int>&visit, int v, int n)
{
    queue<int> q;
    visit[n] = 1;
    q.push(n);

    while (!q.empty())
    {
        int cur = q.front();
        q.pop();
        for (int i = 0; i < arr[cur].size(); i++)
        {
            int next = arr[cur][i];
            if (visit[next] != 0) // 다음 정점이 방문 했더라면
            {
                if (visit[cur] == visit[next]) // 인접한 정점이 같은 집합이라면
                {
                    return false;
                }
            }
            else
            {
                visit[next] = visit[cur] == 1 ? 2 : 1;
                q.push(next);
            }
        }
    }

    return true;
}

int main()
{
    int k;
    cin >> k;

    for (int i = 0; i < k; i++)
    {
        int v, e;
        cin >> v >> e;
        vector<vector<int>> arr(v + 1);
        for (int j = 0; j < e; j++) // 인접 리스트 초기화
        {
            int stt, end;
            cin >> stt >> end;
            arr[stt].push_back(end);
            arr[end].push_back(stt);
        }

        bool answer = true;
        vector<int> visit(v + 1);
        for (int j = 1; j <= v; j++)
        {
            if (visit[j] == 0)
            {
                answer &= BFS(arr, visit, v, j);
            }
        }
        if (answer) cout << "YES\n";
        else cout << "NO\n";
    }
}