【題解】Zerojudge c291 - APCS 2017-0304-2小群體

題目連結

題目大意

給定一些朋友的關係，問有幾個小團體。

題解

我們用並查集維護友好關係。兩個人的關係為好友相當於合併兩個集合。由於每次合併都會使小群體的個數減少 $1$，因此答案為 $n - \text{合併的次數}$。

以下程式碼中並查集只使用了路徑壓縮優化，因此時間複雜度為 $O(n \log n)$。若使用啟發式合併 $+$ 路徑壓縮，則複雜度為 $O(n \alpha(n))$。

#include <bits/stdc++.h>
using namespace std;

struct DSU {
	vector<int> par;

	DSU(int n) : par(n) {
		iota(par.begin(), par.end(), 0);
	}

	int leader(int u) { return par[u] == u ? u : par[u] = leader(par[u]); }

	bool merge(int u, int v) {
		u = leader(u), v = leader(v);
		if(u == v) {
			return false;
		}
		par[u] = v;
		return true;
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	DSU d(n);
	int ans = n;
	for(int i = 0; i < n; i++) {
		int x;
		cin >> x;
		ans -= d.merge(i, x);
	}
	cout << ans << "\n";
	return 0;
}

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】Zerojudge c291 - APCS 2017-0304-2小群體