백준16307 Driver Disagreement

작성일 | In

문제 링크

  • http://icpc.me/16307

문제 출처

  • 2018 BAPC D번

사용 알고리즘

  • BFS
  • Union Find

시간복잡도

  • $O(N log N)$

풀이

대충 BFS를 돌리면 $O(N^2)$라는, TLE 받기 딱 좋은 복잡도가 나옵니다. BFS를 잘 돌려봅시다.

핵심적인 관찰이 있는데, $(a, c)$가 indistinguishable하고, $(c, b)$가 indistinguishable하면 $(a, b)$도 indistinguishable합니다.
이 점을 이용해 union-find와 함께 BFS를 돌려주면 $O(N log N)$ 혹은 $O(N \alpha(N))$에 풀 수 있습니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

struct asdf{
	int a, b, c;
};

int par[101010];

int find(int v){
	return v == par[v] ? v : par[v] = find(par[v]);
}

void merge(int u, int v){
	u = find(u), v = find(v);
	if(u ^ v) par[u] = v;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, a, b; cin >> n >> a >> b;
	vector<asdf> v(n);
	for(auto &i : v) cin >> i.a >> i.b >> i.c;
	for(int i=0; i<101010; i++) par[i] = i;
	queue<asdf> q; q.push({a, b, 0});
	while(q.size()){
		int a = q.front().a;
		int b = q.front().b;
		int c = q.front().c;
		q.pop();
		if(find(a) == find(b)) continue;
		if(v[a].c != v[b].c){
			cout << c; return 0;
		}
		merge(a, b);
		q.push({v[a].a, v[b].a, c+1});
		q.push({v[a].b, v[b].b, c+1});
	}
	cout << "indistingusshable";
}