6장 그래프 - (3) 그래프 탐색 문제 2 - 이분 그래프(1707번)

1. 이분 그래프(Bipartite Graph, 1707번)

- 그래프를 다음과 같이 왼쪽(A), 오른쪽(B) 으로 나눌 수 있으면 이분 그래프라고 한다.

- A에 포함되어 있는 정점끼리 연결된 간선이 없음

- B에 포함되어 있는 정점끼리 연결된 간선이 없음

- 다음 정점의 색을 현재 정점의 색(집합)과 다르게 표시하면서 DFS 탐색을 했을 때, 

- 이분 그래프가 되기 위해서는 나와 연결된 정점들은 나와 다른 색(집합)이어야 한다.

- 나와 연결된 정점이 나와 같은 색(집합)이면 이분 그래프가 아니다.

2. 정답 코드

#include <iostream>

#include <vector>

using namespace std;

vector<int> a[20001];

int check[20001];

// check[i] = 0 : 정점 i 방문하지 않음

//   1 : 정점 i 방문했고, A 집합에 속함

//   2 : 정점 i 방문했고, B 집합에 속함

void dfs(int x, int c) {

check[x] = c;

for (int i = 0; i < a[x].size(); i++) {

int y = a[x][i];

if (check[y] == 0) {

dfs(y, 3 - c);

}

}

}

int main(void) {

int t, n, m;

cin >> t;

while (t--) {

cin >> n >> m;

for (int i = 1; i <= n; i++) {

a[i].clear();

check[i] = 0;

}

for (int i = 0; i < m; i++) {

int u, v;

scanf("%d %d", &u, &v);

a[u].push_back(v);

a[v].push_back(u);

}

for (int i = 1; i <= n; i++) {

if (check[i] == 0) {

dfs(i, 1);

}

}

bool result = true;

for (int i = 1; i <= n; i++) {

for (int j = 0; j < a[i].size(); j++) {

int k = a[i][j];

if (check[i] == check[k]) {

result = false;

}

}

}

printf("%s\n", result ? "YES" : "NO");

}

return 0;

}