Submission #34953862

---

Source Code Expand

#include <bits/stdc++.h>
#define M_PI 3.14159265358979323846
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;
using namespace std;
class UnionFind {
public:
    vector <ll> par; // 各元の親を表す配列
    vector <ll> siz; // 素集合のサイズを表す配列(1 で初期化)

    // Constructor
    UnionFind(ll sz_) : par(sz_), siz(sz_, 1) {
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.resize(sz_, 1);
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }

    // Member Function
    // Find
    ll root(ll x) { // 根の検索
        while (par[x] != x) {
            x = par[x] = par[par[x]]; // x の親の親を x の親とする
        }
        return x;
    }

    // Union(Unite, Merge)
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        // merge technique（データ構造をマージするテク．小を大にくっつける）
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) { // 連結判定
        return root(x) == root(y);
    }

    ll size(ll x) { // 素集合のサイズ
        return siz[root(x)];
    }
};
int main(){

    int N;
    cin >> N;
    vector<int> X(N), Y(N);
    UnionFind Judge(2000*2000+1);
    vector<int> J(2000 * 2000 + 1);
    for (int i = 0; i < N; i++) {
        cin >> X[i] >> Y[i];
        J[(X[i] + 1000) * 2000 + (Y[i] + 1000)] = 1;

    }
    int ans = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (abs(X[i] - X[j]) <= 1 && abs(Y[i] - Y[j] <= 1)) {
                Judge.merge((X[i] + 1000) * 2000 + (Y[i] + 1000), (X[j] + 1000) * 2000 + (Y[j] + 1000));
            }
        }
   
    }
    for (int i = 0; i < 2000 * 2000 + 1; i++) {
        if (Judge.root(i) == i && J[i] == 1)ans++;
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result