UVa 1665 – Islands [并查集+离线处理]

UVa的并查集果然不一样，还得判断四连块，刚开始没往并查集那儿想，后来看到说用到某个数据结构才想到的，并查集应该算是ACM中最基本的数据结构吧。

C++代码：

```#include <bits/stdc++.h>
using namespace std;

struct Node {
int val, r, c;
};
struct Query {
int val, i, ans;
};
const int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
const int maxn = 1024;
int n, m, t, mp[maxn][maxn], pa[maxn*maxn];
bool vis[maxn][maxn];
Node v[maxn*maxn];
Query query[100005];

int Find(int x) { return x == pa[x] ? x : pa[x] = Find(pa[x]); }

inline bool in(int x, int y) {
return x >= 0 && x < n && y >= 0 && y < m;
}
void input() {
scanf("%d%d", &n, &m);
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
scanf("%d", &mp[i][j]);
v[i*m+j].r = i, v[i*m+j].c = j, v[i*m+j].val = mp[i][j];
}
}
sort(v, v + n * m, [](const Node &a, const Node &b) { return a.val > b.val; });
scanf("%d", &t);
for(int i = 0; i < t; ++i) {
scanf("%d", &query[i].val);
query[i].i = i;
}
}
int judge(int x, int y) {
list<int> pas;
for(int i = 0; i < 4; ++i) {
int vx = x+dir[i][0], vy = y+dir[i][1];
if(in(vx, vy) && vis[vx][vy])
pas.push_back(Find(vx * m + vy));
}
pas.sort();
pas.erase(unique(pas.begin(), pas.end()), pas.end());
for(auto i : pas)
pa[i] = x * m + y;
return 1 - pas.size();
}
void solve() {
for(int i = 0; i < maxn*maxn; ++i)
pa[i] = i;
int cnt = 0;
memset(vis, 0, sizeof(vis));
for(int i = t-1, p = 0; i >= 0; --i) {
int cur = query[i].val;
for(; p < n*m && v[p].val > cur; ++p) {
cnt += judge(v[p].r, v[p].c);
vis[v[p].r][v[p].c] = true;
}
query[i].ans = cnt;
}
}
void output() {
for(int i = 0; i < t; ++i)
printf("%d ", query[i].ans);
printf("\n");
}
int main() {
int T; scanf("%d", &T);
while(T--) {
input();
solve();
output();
}
return 0;
}
```