Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

AOJ 2382 - King Slime

問題文 : King Slime

解いている人数が少ない問題はなんかドキドキする(小並)

解法

同じ $x$ 座標または $y$ 座標をもつスライムたちは, 何かしらの方法で全員 1 つになることが出来るので Union-Find で 1 つのグループにしてやる.
こうすると座標を共有しないでかいスライムたちのグループができるが, こいつらは座標を共有しないので盤面の端で合体させる必要がある.
ということで, 答えはスライムたちの連結成分数を m とすると $n - 1 + m $ (1 匹になるまでにスライムたちが併合する回数 + 連結成分数) になるが, さいしょから端にスライムがいる場合と, 連結成分の数が 1 だった場合は答えが 1 小さくなる.

コード

#include <bits/stdc++.h>

using namespace std;

vector<int> Ws[100001], Hs[100001];
int par[40000];

int find(int x)
{
    return (par[x] >= 0 ? par[x] = find(par[x]) : x);
}

void merge(int x, int y)
{
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (-par[x] < -par[y]) swap(x, y);
    par[x] += par[y];
    par[y] = x;
}

int main()
{
    int n, w, h;
    int cw = 0, ch = 0;
    
    scanf("%d %d %d", &n, &w, &h);
    
    for (int i = 0; i < n; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        
        if (a == 1 || a == w) cw = 1;
        if (b == 1 || b == h) ch = 1;
        
        Ws[a].push_back(i);
        Hs[b].push_back(i);
    }
    
    memset(par, -1, sizeof(par));
    for (int i = 1; i <= w; i++){
        for (int j = 1; j < Ws[i].size(); j++){
            merge(Ws[i][j - 1], Ws[i][j]);
        }
    }
    for (int i = 1; i <= h; i++){
        for (int j = 1; j < Hs[i].size(); j++){
            merge(Hs[i][j - 1], Hs[i][j]);
        }
    }
    
    set<int> s;
    for (int i = 0; i < n; i++) s.insert(find(i));
    
    printf("%d\n", s.size() == 1 ? n - 1 : (n - 1 + s.size() - (cw | ch)));
    
    return (0);
}