UnionFind

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/24452 번역 문제 번역 # JOI 연방국에는 1부터 N까지 번호가 매겨진 N개의 도시와, 1부터 M까지 번호가 매겨진 M개의 도로가 있다. 도로 i (1 ≦ i ≦ M)는 도시 Ui와 도시 Vi를 양방향으로 연결하고 있다. JOI 연방국은 1부터 K까지 번호가 매겨진 K개의 주(州)로 이루어져 있다. 도시 j (1 ≦ j ≦ N)는 주 Sj에 속해 있다. 또한, 모든 주는 적어도 하나의 도시를 포함한다.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/31055 번역 문제 번역 # Bessie는 수학 지식을 향상시키기 위해 그래프 이론 강좌를 수강하고 있는데, 다음 문제에서 막혔습니다. 그녀를 도와주세요! 연결된 무방향 그래프가 주어집니다. 정점은 $1\dots N$으로, 간선은 $1\dots M$으로 라벨링되어 있습니다 ($2\le N\le 2\cdot 10^5$, $N-1\le M\le 4\cdot 10^5$). 그래프의 각 정점 $v$에 대해 다음 과정을 수행합니다:

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/3830 🧐 관찰 및 접근 # 두 값의 차이를 트리 형태로 저장한다고 생각하자. 간선에 가중치가 있는 트리가 될 것이다. 두 값 $a, b$가 같은 트리에 있다면 비교 가능하고, 그렇지 않다면 비교 불가능하다. 하지만 이 경우 트리가 직선형이 되면, 최악의 경우 $O(N)$이 걸린다. 우리는 이러한 경우에 UnionFind에서 경로 압축을 하는 방법을 배웠다. 결국 루트까지의 간선 가중치 합을 저장해서 이용하면 된다. 💻 풀이 # 코드 (C++): void solve(){ while(1){ int N, M; cin >> N >> M; if(N + M == 0) break; UnionFind uf(N); while(M--){ char op; cin >> op; if(op == '!'){ int a, b, w; cin >> a >> b >> w; uf.merge(a-1, b-1, w); } else{ int a, b; cin >> a >> b; auto [ra, wa] = uf.find(a-1); auto [rb, wb] = uf.find(b-1); if(ra != rb) cout << "UNKNOWN\n"; else cout << wb - wa << '\n'; } } } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/21932 번역 문제 번역 # 문제 설명 # 무방향 그래프가 주어지고, 각 노드에는 양의 정수 값이 연결되어 있습니다. 임계값(threshold)이 주어지면, 그래프의 노드들은 두 그룹으로 나뉩니다: 하나는 임계값 이하의 값을 가진 노드들로 구성되고, 다른 하나는 나머지 노드들로 구성됩니다. 이제 서로 다른 그룹에 속한 두 노드를 연결하는 모든 간선을 제거하여 얻은 원래 그래프의 부분 그래프를 고려합니다. 두 노드 그룹이 모두 비어있지 않을 때, 주어진 그래프가 연결되어 있는지 여부와 관계없이 결과 부분 그래프는 연결이 끊어집니다.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/18180 번역 문제 번역 # 바이킹 락 운동에는 다양한 흐름이 존재한다. 올드 아이슬란드 그래니트 락, 미들 데니쉬 더스티 바이킹 락, 레이트 핀게일 다크 그린 락, 피오르드 볼더 아발란체 락 등, 인기 있는 흐름의 전체 목록을 나열하면 이 페이지를 여러 번 가득 채울 정도이다. 스칸디나비아 고등교육부는 이러한 흐름들이 서로 어떻게 영향을 주는지 연구하고 있다. 그들은 현재 대규모 실험을 계획 중이며, 적절히 선발된 자원봉사자들을 무인도들로 구성된 군도에 배치하여 상대적으로 긴 시간 동안 그들의 음악적 스타일과 선호도가 서로 미치는 영향을 관찰하고자 한다.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/25567 🧐 관찰 및 접근 # 구간합?을 하려면 결국 완성된 배열이 있으면 좋을거같은데.. 근데 줄이 다를때만 합치니까, 결국 완성된 줄은 고정적으로 존재한다! 오프라인으로 잘 돌면서 처리하면 되는거같다. 줄의 맨앞과 맨뒤가 어딘지 잘 관리하고, 모든 줄이 합쳐지지는 않을 수 있으니 이를 주의하자. 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; int sz = 0; vector<vector<int>> lines; rep(i, 0, N){ int cnt; cin >> cnt; vector<int> line(cnt); rep(j, 0, cnt) cin >> line[j]; lines.push_back(line); sz += cnt; } vector<array<int, 3>> Queries; // {query, a, b} int Q; cin >> Q; rep(i, 0, Q){ int op, a, b; cin >> op >> a >> b; Queries.push_back({op, a, b}); } // lineId[x] = i : x번 사람이 i번째 줄에 속함 vector<int> lineId(sz+1); rep(i, 0, N) for(auto x: lines[i]) lineId[x] = i; UnionFind UF(N), UFrev(N); vector<int> nxt(N, -1); for(auto [op, a, b]: Queries){ if(op == 2) continue; int lineA = lineId[a]; int lineB = lineId[b]; if(UF.find(lineA) != UF.find(lineB)){ // lineA 뒤에 lineB 붙이기 int tailA = UFrev.find(lineA); int headB = UF.find(lineB); nxt[tailA] = headB; UF.merge(lineA, lineB); UFrev.merge(lineB, lineA); } } vector<int> mergedLineId(sz+1); vector<int> mergedLineIdx(sz+1); vector<vector<ll>> pfsum(N); rep(i, 0, N) if(UF.find(i) == i){ vector<int> order; int cur = i; while(cur != -1){ for(auto x: lines[cur]) order.push_back(x); cur = nxt[cur]; } for(int j = 0; j < (int)order.size(); j++){ mergedLineId[order[j]] = i; mergedLineIdx[order[j]] = j; } pfsum[i].resize(order.size()+1); rep(j, 0, order.size()) pfsum[i][j+1] = pfsum[i][j] + order[j]; } // 쿼리 처리 UnionFind UF2(N); for(auto [op, a, b]: Queries){ int lineA = lineId[a]; int lineB = lineId[b]; if(op == 1){ if(UF2.merge(lineA, lineB)) cout << "YES\n"; else cout << "NO\n"; } else{ if(UF2.find(lineA) != UF2.find(lineB)){ cout << "-1\n"; continue; } int mergedLine = mergedLineId[a]; int idxA = mergedLineIdx[a]; int idxB = mergedLineIdx[b]; if(idxA > idxB) swap(idxA, idxB); cout << pfsum[mergedLine][idxB+1] - pfsum[mergedLine][idxA] << "\n"; } } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/1647 🧐 관찰 및 접근 # 집 (정점)과 길 (간선)이 있다. 마을 두개로 분리해야한다. 이 때, 간선의 가중치의 합을 최소화해야한다. 이미 두 집이 한 마을 안에 있다면, 둘이 연결할 필요가 없다. 이미 다른 우회로로 갈 수 있기 때문 연결하던 도중 마을이 두개가 남았다면 끝내면 된다. 크루스칼 알고리즘으로 덩어리가 두개가 남을때까지 반복하면 되겠다. 💻 풀이 # 코드 (C++): void solve(){ int N, M; cin >> N >> M; vector<tuple<int, int, int>> edges; // weight, u, v rep(i, 0, M){ int u, v, w; cin >> u >> v >> w; edges.emplace_back(w, u, v); } UF.init(N+1); sort(all(edges)); int ans = 0; for(auto &[w, u, v]: edges){ if(UF.group == 3) break; if(UF.merge(u, v)) ans += w; } cout << ans << "\n"; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/10775 🧐 관찰 및 접근 # 1번 게이트가 제일 쓰기 좋아보인다. 그러므로 1번 게이트를 아낀다고 생각하면, 모든 비행기를 도킹시킬때 갈 수 있는 최댓값으로 도킹시키면 되는 것 같다. 이를 나이브하게 구현하면 한번당 $O(G)$가 걸릴 것이다. 100000 100000 100000 100000 100000 ... 과 같은 테스트케이스를 생각해보면 된다. 따라서 $\text{calc}(g_i) = g_i$ 보다 작거나 같은 살아있는 게이트의 최댓값을 빠르게 찾으면 된다. 이는 유니온파인드로 빠르게 수행 가능하다! merge할때 자신보다 작은 값을 가리키게 하자. 💻 풀이 # 코드 (C++): void solve(){ int G, P; cin >> G >> P; UF.init(G+1); int ans = 0; while(P--){ int g; cin >> g; int rt = UF.find(g); if(rt == 0) break; UF.merge(rt, rt-1); ans++; } cout << ans << "\n"; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/1043 🧐 관찰 및 접근 # 지민이는 모든 파티에 참여해야하므로, 진실을 아는 사람이 있는 파티의 모든 사람은 진실을 알게 된다. 모든 파티에 대해 진실을 알게 된 사람을 확인한 후, 진실을 아는사람이 없는 파티들의 수를 세면 된다. 유니온 파인드, 분리 집합으로 해결하자. 💻 풀이 # 코드 (C++): void solve(){ int N, M; cin >> N >> M; vector<vector<int>> parties; UnionFind UF(N+1); // 0은 진실을 아는 사람 int cnt; cin >> cnt; rep(i, 0, cnt){ int a; cin >> a; UF.merge(0, a); } rep(i, 0, M){ cin >> cnt; vector<int> party(cnt); rep(j, 0, cnt) cin >> party[j]; parties.push_back(party); rep(j, 0, cnt-1) UF.merge(party[j], party[j+1]); } int ans = 0; for(auto party: parties){ bool flag = true; for(auto p: party) if(UF.find(p) == 0) flag = false; if(flag) ans++; } cout << ans; } 🔒 구현 코드 잠금