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

1707번 : 이분 그래프

---

문제)

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

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

 

 

 

입력 :

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

 

 

 

출력 :

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

 

 

 

 

 

 

풀이)

 

이 문제를 풀면서 2번 실수를 했다.

 

첫 번째는 DFS를 이용하여 푼 것,

정점과 간선의 개수가 매우 많기 때문에 스택이 깊어지게 되고, 메모리 부족이 터질 수 밖에 없다.

 

두 번째는 그래프가 1개라고 생각한 것이다.

그래프가 1개만 나온다고 하지 않았기 때문에 그래프가 2개가 존재할 수도 있다.

따라서 모든 정점에 대해서 확인을 진행해야 한다.

 

// 1707. 이분 그래프
#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
int k;
int v, e;
 
vector <vector<int>> vec;
vector<int> visited;
bool flag = 0;
 
void bfs(int s)
{
    if (visited[s]) return;
 
    queue<int> q;
    visited[s] = 1;
    q.push(s);
 
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
 
        for (int i = 0; i < vec[x].size(); i++)
        {
            int nxt = vec[x][i];
            if (visited[nxt] == 0)
            {
                visited[nxt] = visited[x] * -1;
                q.push(nxt);
            }
            else if (visited[x] == visited[nxt])
            {
                flag = 1;
                return;
            }
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> k;
 
    while (k--)
    {
        cin >> v >> e;
        vec.resize(v + 1, vector<int>());
        visited.resize(v + 1, 0);
 
        int a, b;
        for (int i = 0; i < e; i++)
        {
            cin >> a >> b;
 
            // 무방향 그래프
            vec[a].push_back(b);
            vec[b].push_back(a);
        }
 
        flag = 0;
        for (int i = 1; i < v + 1; i++)
        {
            bfs(i);
        }
 
        if (flag) cout << "NO\n";
        else cout << "YES\n";
 
        vec.clear();
        visited.clear();
    }
 
    return 0;
}
 

---

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

1707번: 이분 그래프