<링크>
https://www.acmicpc.net/problem/1717
<소스코드>
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 | #include<stdio.h> #include<string.h> int parent[1000001]; int find(int i) { if (parent[i] == i) return i; int j = find(parent[i]); parent[i] = j; return j; } void combine(int i, int j) { parent[find(j)] = find(i); } int main() { int N, M; scanf("%d%d", &N, &M); for (int i = 0; i <= N; ++i) parent[i] = i; while (M--) { int a, b, c; scanf("%d%d%d", &a, &b, &c); if (a == 0) combine(b, c); else if (find(b) == find(c)) printf("YES\n"); else printf("NO\n"); } } | cs |
<풀이>
union find로 풀었다.
처음엔 시간초과가 났었다.
1 2 3 4 5 6 7 8 | int find(int i) { if (parent[i] == i) return i; int j = find(parent[i]); parent[i] = j; return j; } | cs |
find할때 부모를 다 갱신해서 부모자식간 depth가 1이 되게끔 갱신해야하는데 처음엔 그걸 빼먹었었다.
예를들어
union(2,3)
unoin(3,4)
unoin(1,2) 순으로 쿼리가 들어오면
4의 부모는 3
3의 부모는 2
2의 부모는 1이 된다.
이때 4의 최종부모를 찾을때(find)는 1까지 거슬러올라가는데 3만큼 시간이 걸리고
3의 최종부모를 찾을때는 2만큼의 시간이 걸리게 되므로 극단적인 그래프가 그려지면 시간이 오래걸린다.
따라서 4의 부모를 find할때 1까지 거슬러올라갔으면 다시 리턴해 내려오면서 2의부모, 3의부모, 4의부모를 다 1로 바꿔줘야한다.
