python/TangDou/XiTi/1413.cpp

#include <bits/stdc++.h>

using namespace std;

#pragma region 并查集模板
int p[101]; //存储元素的父节点
int Rank[101]; //存储树的高度(秩)
//建立并查集
void Build(int n) {
    for (int i = 1; i <= n; ++i) {
        p[i] = i; //父结点是元素自身
    }
}

//查找根结点//路径压缩
int Find(int x) {
    if (p[x] != x)
        p[x] = Find(p[x]);
    return p[x];
}

//按秩合并集合
void Union(int x, int y) {
    x = Find(x);
    y = Find(y);
    if (Rank[x] < Rank[y]) p[x] = y;
    else {
        p[y] = x;
        if (Rank[y] == Rank[x]) Rank[x]++;
    }
}

#pragma endregion 并查集模板

bool comp(const pair<int, int> &a, const pair<int, int> &b) {
    return a.second > b.second;
}

int main() {
    //输入+输出重定向
    freopen("../1413.txt", "r", stdin);

    int n, k;
    cin >> n >> k;

    //建立并查集
    Build(n);

    //合并集合
    for (int i = 1; i <= k; ++i) {
        int a, b;
        cin >> a >> b;
        Union(a, b);
    }

    //多少个家庭
    unordered_map<int, int> _map;
    for (int i = 1; i <= n; ++i) {
        if (_map.count(p[i]) == 0) _map[p[i]] = 1;
        else _map[p[i]]++;
    }
    cout << _map.size() << " ";

    //迭代_map
    //最大家庭人数(采用的技巧，unordered_map的value排序)
    vector<pair<int, int> > b;
    for (auto x:_map) {
        b.push_back(x);
    }
    sort(b.begin(), b.end(), comp);
    cout << b[0].second << endl;
    //关闭文件
    fclose(stdin);
    return 0;
}