UVA 572 油田连通块-并查集解决

题意:8个方向如果能够连成一块就算是一个连通块,求一共有几个连通块。

分析:网上的题解一般都是dfs,但是今天发现并查集也可以解决,为了方便我自己理解大神的模板,便尝试解这道题目,没想到过了。。。

 #include <cstdio>
#include <iostream>
#include <sstream>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#define ll long long
#define mem(m, a) memset(m, a, sizeof(m))
#define repu(i, a, b) for(int i = a; i < b; i++)
#define maxn 1100
const double PI=-acos(-1.0);
using namespace std;
struct Node
{
int val, x, y;
bool operator < (const Node a)const
{
return val > a.val;
}
Node(int v=, int x=, int y=):val(v), x(x), y(y) {}
} nd[maxn*maxn];
struct Query
{
int h, id;
bool operator < (const Query a)const
{
return h>a.h;
}
Query(int h=, int id=):h(h), id(id) {}
} q[];
bool vis[maxn][maxn];
int n, m, pre[maxn*maxn];
const int dx[]= {, , -, , , , -, -};
const int dy[]= {, -, , , , -, , -};
int Find(int x)
{
if(pre[x] == -) return x;
return pre[x] = Find(pre[x]);
}
bool OK(int x, int y)
{
return x && y && x<=n && y<=m;
}
int judge(int x, int y)
{
int v[], cnt=;
for(int i=; i<; i++)///寻找他周围的四个数字是哪些集合的
{
int nx=x+dx[i], ny=y+dy[i];
if(OK(nx, ny) && vis[nx][ny])///已经遍历过的
{
int t = Find(m*(nx-)+ny);
v[cnt++] = t;
}
}
sort(v, v+cnt);
cnt = unique(v, v+cnt)-v;
for(int i=; i < cnt; i++)
pre[v[i]] = m*(x-)+y;///把筛选下来的全都归入(x,y)中
return - cnt;///返回的值也只有-1,0,1
}
int main()
{
char c[][];
int T, t, v;
while(~scanf("%d%d", &n, &m) ,n + m)
{
getchar();
int tot=;
repu(i,,n+)
gets(c[i]);
repu(i,,n+)
{
repu(j,,m)
{
if(c[i][j] == '*')
nd[tot]=Node(, i, j+);
else
nd[tot]=Node(, i, j+);
tot++;
}
}
///都是从大到小
sort(nd, nd+tot);
memset(vis, , sizeof vis);
memset(pre, -, sizeof pre);
int cnt=,j = ;
for(; nd[j].val > && j < tot; j++)
{
///如果这个点比所查询的点大,则可以加入其坐标
cnt += judge(nd[j].x, nd[j].y);
vis[nd[j].x][nd[j].y]=;
}
printf("%d\n",cnt);
}
return ;
}
/*
3 5
*@*@*
**@**
*@*@*
*/

借助的是UVA 1665 大神的模板

上一篇:Python之美[从菜鸟到高手]--NotImplemented小析


下一篇:UVa 1640 (计数) The Counting Problem