Merge pull request encrypted-def#423 from neppiness/20955_1

encrypted-def · web-flow · commit 16048833a48f · 2023-02-20T22:03:13.000+09:00
update: 0x19 20955_1.cpp
diff --git a/0x19/solutions/20955_1.cpp b/0x19/solutions/20955_1.cpp
@@ -0,0 +1,54 @@
+// Authored by : scsc3204
+// Co-authored by : BaaaaaaaaaaarkingDog
+// http://boj.kr/ae6be2f242b44089a06fe25b5700ac0b
+#include <bits/stdc++.h>
+using namespace std;
+
+const int MX = 100'000;
+
+int n, m;
+int cnt, p[MX + 2];
+
+int find(int x) {
+  if(p[x] < 0) return x;
+  return p[x] = find(p[x]);
+}
+
+void try_merge(int u, int v) {
+  u = find(u); v = find(v);
+  if(u == v) { cnt++; return; }
+  if(p[u] > p[v]) swap(u, v);
+  p[u] += p[v];
+  p[v] = u;
+}
+
+int main() {
+  ios::sync_with_stdio(0);
+  cin.tie(0);
+
+  cin >> n >> m;
+  fill(p, p+n+1, -1);
+  for(int i = 0; i < m; i++) {
+    int u, v; cin >> u >> v;
+    try_merge(u, v);
+  }
+
+  cout << n - m - 1 + 2*cnt;
+}
+/*
+유니온 파인드를 활용한 별해입니다.
+
+간선을 입력 받으면서 merge를 시도합니다.
+두 정점의 부모가 동일하지 않다면 merge를 수행합니다.
+두 정점의 부모가 동일한 경우
+해당 간선은 불필요한 간선이므로
+자르는 연산 횟수인 cnt를 증가시킵니다.
+
+이 연산을 완료한 뒤에 남은 간선 수는 총 (m - cnt)개가 됩니다.
+여기서 간선을 연결해 (n - 1)개의 간선을 확보해야 트리가 구성됩니다.
+따라서 연결해야 하는 간선 수는 (n - 1) - (m - cnt)개가 됩니다.
+
+그러므로 간선을 잇고 자르는 총 연산 수는
+(n - 1) - (m - cnt) + cnt = n - m - 1 + 2*cnt이며,
+이를 답으로 출력합니다.
+*/
