题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1010;
int p[N * N];
int m, n;

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n * m; i ++) p[i] = i;
    int x1, y1, x2, y2;
    while(cin >> x1 >> y1 >> x2 >> y2)
    {
        int a = (x1  - 1) * m + y1 - 1, b = (x2 - 1) * m + y2 - 1;
        p[find(a)] = find(b);
    }

    int res = 0;

    for (int a = 0; a < (n - 1) * m; a ++)
    {
        int x = a / m, y = a % m;
        int b = (x + 1) * m + y;
        int pa = find(a), pb = find(b);
        if (pa != pb)
        {
            res ++;
            p[pa] = pb;
        }
    }

    for (int a = 0; a < n * m; a ++)
    {
        int x = a / m, y = a % m;
        if (y < m - 1)
        {
            int b = x * m + y + 1;
            int pa = find(a), pb = find(b);
            if (pa != pb)
            {
                res += 2;
                p[pa] = pb;
            }
        }
    }
    cout << res;
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla