1707 - 이분 그래프
본문
그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.
그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 $K$가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 $V$와 간선의 개수 $E$가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 $1$부터 $V$까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 $E$개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호 $u, v$ ($u \neq v$)가 빈 칸을 사이에 두고 주어진다.
출력
$K$개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 2sec | 256MB |
- $2 \leq K \leq 5$
- $1 \leq V \leq 20\,000$
- $1 \leq E \leq 200\,000$
풀이
‘이분 그래프’ 라는 개념 자체가 이미 잘 정의되어 있는 개념이었다. 자세한 설명은 하지 않을 예정이니, 궁금하면 직접 찾아보도록 하자.
이분 그래프의 조건을 자세하게 생각해보자. 아무 노드나 하나 선택하면, 그 노드와 직접 연결되어 있는 노드들은 서로 직접 연결되어있으면 안된다. 그러나, 그 노드 사이에 또 다른 노드가 있다면 그 경우는 또 가능한 경우이다. 이렇게 계속 경우를 늘려나가다 보면 얻을 수 있는 정보는 “길이가 1을 제외한 홀수인 사이클은 존재할 수 없다“가 된다. 길이가 짝수인 사이클은 가능.
다만 위 정보는 참고용일 뿐, 이분 그래프의 정의만을 이용해서도 해답을 찾을 수 있다. 아무 노드 $x$를 선택하여 그 노드를 $A$그룹이라고 칭하면, $x$와 직접 연결된 다른 모든 노드를 $B$그룹으로 정하는 것이다. $B$그룹의 노드들과 직접 연결된 모든 노드들은 다시 $A$그룹이라고 칭하고, 이 과정을 반복하는 것이다. 그러다가 같은 그룹의 두 노드가 직접 연결되는 경우가 존재한다면, 그 그래프는 이분 그래프가 될 수 없다는 점을 이용한다.
이것은 bfs를 이용하여 구현할 수 있다. 앞서 얘기했던 방법처럼, 한 노드 $x$를 선택하고 그것을 First 그룹에 넣는다. 이후 bfs를 진행하여 직접 연결된 모든 노드를 Second 그룹에 넣고, 다음 탐색을 진행한다. 어떤 노드 $a$는 이전에 탐색했고 직접 연결된 노드의 그룹에 따라 본인의 그룹이 정해지고, 만약 불가능한 그룹 분배가 나온다면 이분 그래프가 불가능하다고 반환한다.
다만, 문제에서 주어지는 입력들의 경우, 노드들의 그래프가 1개가 아닐 수 있다. 즉 여러 개의 그래프가 존재하므로, 각각의 그래프에 대해서 탐색을 진행하면 된다. bfs 한번에 그래프 1개만을 탐색하므로, 탐색되지 않은 다른 노드에서 추가 탐색을 진행해야한다. 이것은 테스트케이스 안의 visit 배열을 이용하도록 하자.
- 참고 알고리즘 : BFS 탐색
코드
사용 언어 : C
최종 수정일 : 2023 / 9 / 8
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <stdio.h>
#include <stdlib.h>
typedef char bool;
const bool true = 1;
const bool false = 0;
typedef struct Pair {
int first, second;
} pair;
typedef struct QueueNode {
int idx, g;
} QN;
typedef struct Node {
int x;
struct Node* next;
} ND;
#define MAX_IDX (20000 + 1)
#define MAX_EDGE 200000
const int EMPTY = 0;
const int FIRST = 1;
const int SECOND = 2;
ND* adjacency_list[MAX_IDX + 1];
int v, e;
int group[MAX_IDX + 1];
ND* createNewNode(int x) {
ND* node = (ND*)malloc(sizeof(ND));
node->x = x;
node->next = NULL;
return node;
}
void free_all() {
for (int i = 1; i <= v; ++i) {
ND* cur = adjacency_list[i];
while (cur != NULL) {
adjacency_list[i] = cur->next;
free(cur);
cur = adjacency_list[i];
}
}
return;
}
void init() {
for (int i = 1; i <= v; ++i) {
adjacency_list[i] = NULL;
group[i] = EMPTY;
}
return;
}
void read_input() {
scanf("%d %d", &v, &e);
while (e--) {
int a, b;
scanf("%d %d", &a, &b);
ND* newNode = createNewNode(b);
newNode->next = adjacency_list[a];
adjacency_list[a] = newNode;
newNode = createNewNode(a);
newNode->next = adjacency_list[b];
adjacency_list[b] = newNode;
}
return;
}
bool bfs(int x) {
QN q[MAX_IDX + 1];
int front = 0, rear = 0;
q[rear++] = (QN){x, group[x]};
while (front < rear) {
QN cur = q[front++];
ND* point = adjacency_list[cur.idx];
while (point != NULL) {
int target = point->x;
if (group[target] == group[cur.idx]) {
return false;
} else if (group[target] == EMPTY) {
group[target] = (FIRST + SECOND) - group[cur.idx];
q[rear++] = (QN){target, group[target]};
}
point = point->next;
}
}
return true;
}
bool solve() {
for (int i = 1; i <= v; ++i) {
if (group[i] == EMPTY) {
group[i] = FIRST;
if (bfs(i) == false) {
return false;
}
}
}
return true;
}
int main() {
int k;
scanf("%d", &k);
while (k--) {
init();
read_input();
printf("%s\n", solve() ? "YES" : "NO");
free_all();
}
return 0;
}