http://blog.sina.com.cn/s/blog_4c396f430100cort.html
嗯……最近好好学了下并查集……以弥补我远不过关的数据结构……(其实学了并查集我的数据结构还是远不过关……)
首先要说的是……我现在才学会的东西,逆铭大牛牛早在几年前就学会了……大家可以参考他的博客
……
那么,并查集是一种对不相交集合的数据结构,它支持两种操作:
通常并查集可以用森林或者是链表来实现,但是通常链表实现效率不如森林实现,所以通常使用并查集的森林实现,这时,每个集合其实就是一棵树,并且这个集合就用这颗树的树根来标识。
可以用数组来表示森林,用p[i]表示结点i的父结点。初始的时候让每个结点的父结点指向其自身,即p[i] =
i,每个结点就是一个单独的集合。那么合并两个元素x,y所在的集合,就可以先把x和y所在集合的标识,即其树根计算出来,设为p_x,p_y,然后再让p_y的父结点指向p_x即可,即p[p_y]
= p_x。下面的函数合并了两个元素x,y所在的集合:
void union_set(int x,
int y) {
int
p_x = get_parent
(x),
p_y = get_parent(y);
p[p_y] =
p_x;
}
|
在查找一个元素属于哪个集合,即查找这个元素的根结点的时候,如果这个元素的父结点就是其自身,即这个元素本身就是根结点,那么查找结束,返回其本身。否则返回这个元素父结点的根结点。这里有一个称为路径压缩的优化,就是在查找这个元素的根结点时,把其到根结点的路径上的所有点都直接连接到根结点上,可以防止树退化成链。所以可以用递归来实现(不用递归效率更高,读者可以尝试自行完成……)。下面的函数返回结点k的根结点,同时进行路径压缩:
int get_parent(int k)
{
return p[k]
== k ? k : (p[k] = get_parent(p[k]));
}
|
还有一个优化叫做按秩合并,就是总是在合并两个集合的时候总是把深度小的树合并到深度大的树里面,以防止树退化成链。这里我没有提供代码(其实代码也相当简单),具体请大家参考CLRS……
综上,并查集的实现可以是如下的代码:
struct uf_set {
int
p[0xffff];
void clear()
{
for (int i = 0; i < 0xffff; ++i)
p[i] = i;
}
int
get_parent(int k) {
return p[k] == k ? k : (p[k] = get_parent(p[k]));
}
void
union_set(int x, int y) {
int p_x = get_parent(x), p_y = get_parent(y);
p[p_y] = p_x;
}
};
|
有关并查集更详细的内容请参考CLRS或者黑书……下面说三道题目:
这个题没什么说的了,就是最裸的并查集,统计与0属于同一个集合的结点数即可。
代码如下:
#include
<cstdio>
using namespace
std;
struct uf_set {
int
p[30000];
void clear()
{
for (int i = 0; i < 30000; ++i)
p[i] = i;
}
int
get_parent(int k) {
return p[k] == k ? k : (p[k] = get_parent(p[k]));
}
void
union_set(int x, int y) {
int p_x = get_parent(x), p_y = get_parent(y);
p[p_y] = p_x;
}
};
int n, m, ans;
uf_set union_find_set;
int main() {
for
(scanf("%d%d", &n, &m); n != 0;
scanf("%d%d", &n, &m)) {
union_find_set.clear();
for (int i = 0, num, id1, id2; i < m; ++i) {
scanf("%d%d", &num, &id1);
for (int j = 1; j < num; ++j) {
scanf("%d", &id2);
union_find_set.union_set(id1, id2);
}
}
int group0 = union_find_set.get_parent(0);
ans = 0;
for (int i = 0; i < n; ++i)
if (union_find_set.get_parent(i) == group0)
++ans;
printf("%d\n", ans);
}
return
0;
}
|
这个题是并查集的扩展。可以这样考虑:如果[s,
t]这个区间内数的和为even,那么表示[0, s - 1]和[0, t](简记为s -
1和t)是奇偶性相同的,反之就是奇偶性不同的。但是我们在处理这个问题的时候没有必要像处理一般并查集问题一样把奇偶性相同的合并,把奇偶性不同的处理
为不同的集合。而是把所有已经发生了关系的集合都统统合并,并为每个元素都增加一个域p_r[i]表示结点i与其父亲结点(p[i])的关系是
p_r[i],p_r[i]
= 1表示其与父结点的奇偶性相同,p_r[i] =
0表示奇偶性不同。那么只需要稍微思考一下在合并集合的时候(有两种:一种是奇偶性相同的集合合并,一种是奇偶性不同的集合合并)怎么维护p_r域就可以
了。还需要注意的是因为lenth太大(最大为1000000000),而questions
and
answers比较小(最大为5000),所以需要在读入数据以后进行离散化(当然是离散化三部曲:sort、unique、lower_bound
了!)。具体的实现细节请参考代码。
代码如下(URAL的):
#include
<cstdio>
#include <cstring>
#include <algorithm>
using namespace
std;
struct question {
int s,
t;
char
f;
};
struct uf_set {
int
p[10000], p_r[10000];
void clear()
{
for (int i = 0; i < 10000; ++i) {
p[i] = i;
p_r[i] = 1;
}
}
int
get_parent(int k) {
if (p[k] == k)
return k;
int tmp = get_parent(p[k]);
p_r[k] = 1 ^ p_r[p[k]] ^ p_r[k];
return p[k] = tmp;
}
bool
set_same(int x, int y) {
int p_x = get_parent(x), p_y = get_parent(y);
if (p_x == p_y)
return p_r[x] == p_r[y];
p[p_y] = p_x;
p_r[p_y] = 1 ^ p_r[x] ^ p_r[y];
return true;
}
bool
set_diff(int x, int y) {
int p_x = get_parent(x), p_y = get_parent(y);
if (p_x == p_y)
return p_r[x] != p_r[y];
p[p_y] = p_x;
p_r[p_y] = p_r[x] ^ p_r[y];
return true;
}
};
int l, n, num[10000],
ans;
question q[5000];
uf_set union_find_set;
int main() {
char
buf[10];
for
(scanf("%d", &l); l != -1; scanf("%d",
&l)) {
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d%d%s", &q[i].s, &q[i].t,
buf);
--q[i].s;
q[i].f = buf[0];
num[i * 2] = q[i].s;
num[i * 2 + 1] = q[i].t;
}
sort(num, num + n * 2);
l = unique(num, num + n * 2) - num;
for (int i = 0; i < n; ++i) {
q[i].s = lower_bound(num, num + l, q[i].s) - num;
q[i].t = lower_bound(num, num + l, q[i].t) - num;
}
union_find_set.clear();
for (ans = 0; ans < n; ++ans) {
if (q[ans].f == 'e') {
if (!union_find_set.set_same(q[ans].s, q[ans].t))
break;
} else if (q[ans].f == 'o') {
if (!union_find_set.set_diff(q[ans].s, q[ans].t))
break;
}
}
printf("%d\n", ans);
}
return
0;
}
|
同样是并查集的扩展,和上一题目差不多,只不过p_r[i]有三种取值了:p_r[i] = 0表示种类相同,p_r[i] =
1表示i吃i的父结点,p_r[i] = -1表示i被i的父结点吃。只需要搞清楚合并集合以后p_r的取值就可以了。
代码如下:
#include
<cstdio>
#include <cstring>
using namespace
std;
struct uf_set {
int
p[50000], p_r[50000];
void clear()
{
for (int i = 0; i < 50000; ++i) {
p[i] = i;
p_r[i] = 0;
}
}
int
get_relation(int x, int y) {
if (x == -1 && y == -1)
return 1;
if (x == 1 && y == 1)
return -1;
return x + y;
}
int
get_parent(int k) {
if (p[k] == k)
return k;
int tmp = get_parent(p[k]);
p_r[k] = get_relation(p_r[k], p_r[p[k]]);
return p[k] = tmp;
}
bool
set_same(int x, int y) {
int p_x = get_parent(x), p_y = get_parent(y);
if (p_x == p_y)
return p_r[x] == p_r[y];
p_r[p_y] = get_relation(-p_r[y], p_r[x]);
p[p_y] = p_x;
return true;
}
bool
set_eat(int x, int y) {
int p_x = get_parent(x), p_y = get_parent(y);
if (p_x == p_y)
return get_relation(p_r[x], -p_r[y]) == 1;
p_r[p_y] = get_relation(-p_r[y], get_relation(-1, p_r[x]));
p[p_y] = p_x;
return true;
}
};
int n, m, ans;
uf_set union_find_set;
int main() {
scanf("%d%d", &n, &m);
union_find_set.clear();
for (int i =
0, d, x, y; i < m; ++i) {
scanf("%d%d%d", &d, &x,
&y);
if (x > n || y > n) {
++ans;
continue;
}
if (d == 1) {
if (!union_find_set.set_same(x - 1, y - 1))
++ans;
} else if (d == 2) {
if (!union_find_set.set_eat(x - 1, y - 1))
++ans;
}
}
printf("%d\n", ans);
return
0;
}
|
发现写ACM相关的东西好累的说……希望对大家有用……
分享到:
相关推荐
base zz zz zz zz zz base zz zz zz zz zz base zz zz zz zz zz base zz zz zz zz zz
ZZ561401.CAB ZZ561401.CAB ZZ561401.CAB
wincc SIMATIC WinCC是第一个使用最新的32位技术的过程监视系统,具有良好的开放性和灵活性。 从面市伊始,用户就对SIMATIC WinCC印象深刻。
使用LoopSim方法,我们合并ZZ和ZZ + jet的NLO QCD结果,并获得ZZ产生的近似NNLO预测。 还包括对ZZ过程的精确胶子融合环平方的贡献。 最重要的是,我们将来自胶子-胶子通道的胶子-融合ZZ + jet贡献添加到我们的合并...
在CAD中想要快速测量长度,在CAD工具栏找到加载应用程序,再点击加载 加载成功后在输入栏输入“zz”(不分大小写)在选择你需要测量的线段即可。
,主图指标,顶底信号,突破,转折信号,都很明显
程序员的编辑器——VIM(zz) - 饮水思源
留言本改自柏图留言本 BTB 1.2 管理员:zz809 密 码:zz809.com
ZZ公司安全生产守则.docx
zz_layer.il是源代码,install.bat是安装的 使用举例:zz 1-3 4 126 127 层号定义,与PADS类似:1~120是etch ;SolderMask: 121(top) 128(bot) ;Silkscreen: 126(top) 129(bot) ;Assembly: 127(top) 130(bot) ;Paste...
zz;ldkfjntmtmsbggyyessdd
android应用源码zz-doctor中医大夫助理信息系统
基于国家标准的endnote的输出样式,适用于学生党论文插入文献参考,较为方便。endnote论文神器。
zz机械手册
ZZ Fibo Trader 简单地展示了 Simple ZZ Fibo 的使用, 它在之字转向的波动中绘制斐波那契线。另外,算法还展示了通过抛物线系统进行移动止损的操作。
新东方flash课件必备播放器
cad标高归零,好用的
C语言第8章_zz指针 详细的讲解了指针 这一节
ZZ-2021030 网络搭建与应用赛项赛卷《网络环境》.pdf
博途V16授权 博途V16授权 博途V16授权 博途V16授权 TIA V16 AX NF ZZ TIA V16 AX NF ZZ TIA V16 AX NF ZZ TIA V16 AX NF ZZ TIA V16 AX NF ZZ