【 Ubiquitous Religions】uva 解题 3/4 (union-find)

题目连结

解题

如果两个值map都没有这个值就把他们串起来（其中一个自己当父节点）如果其中一个有，另一个没有，把没有的串到有的如果都有，用merge串起来

最后，用for each找共有几个父节点

#include <iostream>#include <map>#include <vector>#include <set>using namespace std;int Find_(vector<int> &f, int x){    if (f[x] != x)        f[x] = Find_(f, f[x]);    return f[x];}void merge(vector<int> &f, vector<int> &nums, int x, int y){    x = Find_(f, x);    y = Find_(f, y);    if (x == y)        return;    if (nums[x] < nums[y])        swap(x, y);    f[y] = x;    nums[x] += nums[y];}int main(int argc, char const *argv[]){    int n, m;    cin >> n >> m;    int turn = 1;    while (n != 0 && m != 0)    {        vector<int> f(n + 1), size(n + 1);        for (int i = 0; i <= n; i++)        {            f[i] = i;            size[i] = 1;        }        map<int, int> have;        for (int i = 0; i < m; i++)        {            int a, b;            cin >> a >> b;            if (have.count(a) && !have.count(b))            {                merge(f, size, b, have[a]);                have[b] = a;            }            else if (!have.count(a) && have.count(b))            {                merge(f, size, a, have[b]);                have[a] = b;            }            else if (!have.count(a) && !have.count(b))            {                f[b] = a;                have[a] = a;                have[b] = a;            }            else if (have.count(a) && have.count(b))            {                merge(f, size, a, b);            }        }        set<int> ans;        for (int i = 1; i <= n; i++)        {            ans.insert(Find_(f, i));        }        cout << "Case " << turn << ": " << ans.size() << endl;        turn++;        cin >> n >> m;    }    return 0;}