蓝桥杯2017年第八届真题-合根植物(C++)

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;

int p[N];

int getFather(int x) {

    if (x != p[x]) {

        p[x] = getFather(p[x]);

    }

    return p[x];

}

int main()

{

    int a, b;

    int res = 0;

    int m, n, k;

    cin >> m >> n >> k;

    int total = m * n;

    for (int i = 1; i <= total; i++) {

        p[i] = i;

    }

    for (int i = 0; i < k; i++) {

        cin >> a >> b;

        int fA = getFather(a);

        int fB = getFather(b);

        if (fA != fB) {

            p[fB] = p[fA];

        }

    }

    unordered_set<int> s;

    for (int i = 1; i <= total; i++) {

        int f = getFather(i);

        if (s.count(f) == 0) {

            res++;

            s.insert(f);

        }

    }

    cout << res << endl;

    return 0;

}