杭電1856——并差集

原題傳送門，并差集的簡單介紹，大佬并差集詳解。
解題思路：
這個算并差集的裸題吧。先將輸入的數(shù)據(jù)（還沒有連接的數(shù)據(jù)）全部用meg函數(shù)連起來，然后用fin函數(shù)遍歷每個男孩最上面的父親，用ans數(shù)組記錄最上面的父親出現(xiàn)的次數(shù)（ans[i]=9：i是幾個人的父親）；然后遍歷ans數(shù)組，找出最大的值就是答案。

注意：
1、fin函數(shù)有很多種寫法，這里我建議用路徑壓縮，沒用路徑壓縮的，還沒試過，不知道能不能ac。
2、數(shù)據(jù)上限是10^7，如果開三個1e7的數(shù)組會爆空間的，因此，我只開了兩個數(shù)組：id，記錄父親（這個是必須的）；ans，記錄父親出現(xiàn)的次數(shù)。

ac代碼

# include <iostream> # include <algorithm> # include <cstdio> # include <cstdlib> # include <string> # include <cstring> # include <vector> using namespace std;const int maxn = 1e7 + 5; int id[maxn]; int ans[maxn];int fin(int x) {return id[x] = id[x] == x ? x : fin(id[x]); } void meg(int x, int y) {int a = fin(x);int b = fin(y);if (a < b) {id[a] = b;}else {id[b] = a;} } bool same(int x, int y) {return fin(x) == fin(y); }int main() {ios::sync_with_stdio(false);//freopen("mainin.txt", "r", stdin);int n;while (cin >> n) {for (int i = 0; i < maxn; i++) {id[i] = i;}memset(ans, 0, sizeof(ans));while (n--) {int a, b;cin >> a >> b;if (!same(a, b)) {meg(a, b);}}for (int i = 0; i < maxn; i++) {ans[fin(i)]++;}int mx = -1;for (int i = 0; i < maxn; i++) {mx = mx > ans[i] ? mx : ans[i];}cout << mx << endl;;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的杭电1856——并差集的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。