[종만북] 문제: EDITORWARS
서론
문제 설명
어떤 임의의 원소가 같다와 다르다라는 정보가 $m(1 \leq m \leq 100000)$개 제공되고, 원소의 개수는 $n(1 \leq n \leq 10000)$개 입니다.
원소의 상태가 2개라면, 같은 원소의 최대 크기를 구하시오, 만약 입력에 모순이 존재한다면, 모순이 존재함을 출력하시오.
문제 유형
이분 그래프 판별(bipartite graph check)문제를 풀어봅시다.
bipartite union-find 방법을 이용하여 풀 수 있습니다.
너무 어려워
Union-Find 기법과 이분 그래프 문제를 합친 문제여서 난이도가 좀 있습니다.
그래서 이걸 자력으로 풀진 못했고, 교과서 코드를 리뷰하겠습니다.
아이디어
원소의 상태가 2개기 때문에, 다음과 같은 사실을 얻을 수 있습니다.
상태를 $State()$로 정의하겠습니다.
- $State(a) = State(b), State(b) \neq State(c) \Rightarrow State(a) \neq State(c)$
- $State(a) \neq State(b), State(b) \neq State(c) \Rightarrow State(a) = State(c)$
이 내용을 정리하면, 각 집합마다 적대 관계인 집합을 얻을 수 있다는 것입니다.
이는 이분 그래프(bipartite graph)의 기본 구조와 동일합니다.
bipartite Union-find
근데 왜 갑자기 union-find기법을 사용해야 할까요?
왜냐하면, 각 원소가 어느 집합에 속하는지(상태가 같은지, 다른지)를 빠르게 판단할 수 있는 대표적인 방법이 Union-find기법인 것입니다.
그러면 이분 그래프에 Union-find기법을 적용시켜봅시다.
일반적인 Union-find처럼 단순히 집합을 합치는 것 외에,
bipartite Union-find는 각 원소가 두 가지 그룹 중 어디에 속하는지 알려주는 정보를 관리해야 합니다.
생각을 정리해보면, 우리는 정보를 저장할 배열을 몇 개 선언할 수 있습니다.
아래 3개는 일반적인 Union-Find를 쓰기 위한 배열입니다.
$parent[x]$: 노드 $x$의 부모 노드입니다.
$rank[x]$: 노드 $x$의 $rank$입니다. merge 연산에 쓰임
$size[x]$: 노드 $x$의 $size$(루트 포함 노드의 개수)입니다.
우리는 여기서 추가적인 배열을 선언해야 합니다.
$enemy[x]$: $x$가 루트라면, 해당 집합과 반대인 집합의 루트 번호입니다. (없으면 -1)
이후에는, 앞서 설명한 상태를 이용해
나와 다른 상태의 원소와 다른 상태의 원소는 나랑 같은 원소, 나와 같은 상태의 원소와 다른 상태의 원소는 나랑 다른 원소를 이용해 bipartite Union-find를 구현하면 되겠습니다.
이때! enemy[]가 쓰입니다.
알고리즘 구상
알고리즘 설계
- 먼저 Union-Find를 쓰기 위해 배열들을 전처리합니다.
- 친구 관계와 적대 관계에 대해 Union-find를 합니다. 모순이 있다면 모순을 발견합니다.
- 이후 부모 원소에 대해 부모와 상태가 같은 원소, 다른 원소의 크기의 최댓값을 결과에 더합니다.
- 이렇게 n개의 원소에 대해 반복하며, 나올 수 있는 최댓값을 출력합니다.
시간 복잡도
전처리하는 함수 Init()의 시간 복잡도는 $O(n)$.
모든 노드를 순회하며, 나올 수 있는 최대 원소의 수를 세어서 시간 복잡도는 $O(n)$.
$merge()$와 $find()$의 시간 복잡도는 $O(α(n))$, 거의 $O(1)$이라 볼 수 있기에(엄밀하진 않습니다)
입력이 $m$개가 주어져 이것에 대한 연산 처리 $m \times O(1) = O(m)$으로
총 시간 복잡도는 $O(n + m)$입니다.
알고리즘 구현
Union-find의 기본 함수
init(), Union-find를 구현할 때 필요한 배열들을 전처리합니다.
1
2
3
4
5
6
7
8
void init() {
parent.clear();
parent.resize(n);
iota(parent.begin(), parent.end(), 0);
r.assign(n, 0);
enemy.assign(n, -1);
s.assign(n, 1);
}
find(), 각 원소의 부모를 찾고, 경로 압축을 합니다.
1
2
3
4
int find(int u) {
if (parent[u] == u) return u;
return parent[u] = find(parent[u]);
}
merge, 두 원소를 rank[]를 기준으로 합병합니다.
특이하게, 원소 2개가 없을 경우를 대비하여 이 코드를 작성합니다.
1
if (u == -1 || v == -1) return max(u, v);
이 코드는 나중에 ack()를 구현할 때 필요합니다!
1
2
3
4
5
6
7
8
9
10
int merge(int u, int v) {
if (u == -1 || v == -1) return max(u, v);
u = find(u), v = find(v);
if (u == v) return u;
if (r[u] > r[v]) swap(u, v);
if (r[u] == r[v]) r[v]++;
parent[u] = v;
s[v] += s[u];
return v;
}
친구, 적대 관계 파악 함수
dis(), 친구 관계인 두 노드를 합병하고 하고, 이로 인해 생긴 적대 관계도 관리하는 함수입니다.
만약 관계의 모순이 발생하면, false를 리턴합니다.
1
2
3
4
5
6
7
8
bool ack(int u, int v) {
u = find(u), v = find(v);
if (enemy[u] == v) return false;
int a = merge(u, v), b = merge(enemy[u], enemy[v]);
enemy[a] = b;
if (b != -1) enemy[b] = a;
return true;
}
dis(), 적대 관계인 두 노드를 합병하고, 이로 인해 생긴 적대 관계도 관리하는 함수입니다.
만약 관계의 모순이 발생하면, false를 리턴합니다.
1
2
3
4
5
6
7
8
bool dis(int u, int v) {
u = find(u), v = find(v);
if (u == v) return false;
int a = merge(u, enemy[v]), b = merge(enemy[u], v);
enemy[a] = b;
enemy[b] = a;
return true;
}
main()
앞서 구현한 Union-find를 구현합니다.
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
int main() {
fastIO;
int C;
cin >> C;
while (C--) {
cin >> n >> m;
init();
string cache;
int a, b, failedIndex = -1;
bool fail = true;
for (int i = 1; i <= m; i++) {
cin >> cache >> a >> b;
if (cache[0] == 'A')
fail = ack(a, b);
else
fail = dis(a, b);
if (!fail && failedIndex == -1) failedIndex = i;
}
int ret = 0;
for (int i = 0; i < n; i++) {
if (parent[i] == i) {
int e = enemy[i];
if (e > i) continue;
int mySize = s[i];
int enemySize = e == -1 ? 0 : s[e];
ret += max(mySize, enemySize);
}
}
if (failedIndex != -1)
cout << "CONTRADICTION AT " << failedIndex << "\n";
else
cout << "MAX PARTY SIZE IS " << ret << "\n";
}
return 0;
}
최종 코드
여기에서 확인하세요!