A. Ice Skating(分块 -- 并查集)

发布于:2022-11-06 ⋅ 阅读:(293) ⋅ 点赞:(0)

题面如下:

在这里插入图片描述

思路 or 题解

X 或 Y 相同的点
可以直接相互到达,不需要添加额外的点进行“转向”
所以可以用分块的思想去思考问题
答案就是:块的个数 - 1

AC代码如下:

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <bitset>
#include <set>
#include<random>
#include<ctime>
#include <queue>
#include <stack>
#include <climits>
#define buff                     \
    ios::sync_with_stdio(false); \
    cin.tie(0);
//#define int long long
//#define ll long long
#define PII pair<int, int>
#define px first
#define py second
typedef std::mt19937  Random_mt19937;
Random_mt19937  rnd(time(0));
using namespace std;
const int N = 100009;
int n;
PII s[N];
int f[N];
int find(int x)
{
    return x == f[x] ? f[x] : f[x] = find(f[x]);
}
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        f[i] = i;
        int a, b;
        cin >> a >> b;
        s[i] = {a, b};
    }
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
        {
            if (s[i].px == s[j].px || s[i].py == s[j].py)
            {
                if (find(i) != find(j))
                    f[find(i)] = find(j);
            }
        }

    int ans = 0;
    for (int i = 1; i <= n; i++)
        if (f[i] == i)
            ans++;

    cout << ans - 1 << '\n';
}
int main()
{
    buff;
    solve();
}
本文含有隐藏内容,请 开通VIP 后查看

网站公告

今日签到

点亮在社区的每一天
去签到