简单并查集

[BZOJ 1529] POI2005 ska Piggy banks

[Description]

n个存钱罐，只能用钥匙打开或砸开。每个存钱罐有一把钥匙，放在任意一个存钱罐中，问最少要砸开多少个存钱罐才能打开所有存钱罐。

[Hint]

$n≤10^6$

[Solution]

打了Tarjan缩点统计度为0的点数然后喜闻乐见地MLE了…然而并查集不知道优越到哪里去了…
发现每个点有且仅有一个前驱，所以连通块的形状一定是一个环或者一个环从某点长出一条链…
然后统计连通块个数就可以了…

[BZOJ 2079] POI2079 Guild

[Description]

给出一个n个点m条边的无向图，现在要进行黑白染色，要满足某个点要与自己不同颜色的点相连，问是否能做到。

[Hint]

$n≤2⋅10^5,m≤5⋅10^5$

[Solution]

傻逼题…
对一个连通块求任意一棵生成树然后分层染色就是合法的方案。
不合法当且仅当存在大小为1的连通块。

[BZOJ 1116] POI2008 CLO

[Description]

给出一个n个点m条边的无向图。现在可以将一些边变成有向边，问可不可以做到每个点有且只有一条有向入边。

[Hint]

$n≤10^5,m≤2⋅10^5$

[Solution]

我们发现一个连通块中若存在环整个连通块就可行，依次判断即可。
用并查集尤为方便：另开一个数组记录以某个点为根的并查集存不存在环，若某条边的两个点在同一个并查集中，将这个并查集的根标为true.
最后只用判断是否所有根都为true即可。

[BZOJ 1854] SCOI2010 游戏

[Description]

n个物品，每个物品有两个属性值a,b，分别为1~10000的一个整数。每种物品仅可以发挥出一种属性值。
问最大的x，使得[1,x]所有属性值的物品都存在。

[Hint]

$n≤10^6$

[Solution]

听说能用并查集做…
把属性值定义为点，同一物品的属性a,b看边(a,b)，这样建成一个图。
我们需要“为每条边选一个指向，使得被指向的点尽量多”。是不是有点像上一题了呢？但并不尽相同。
若一个连通块存在环，同样还是所有点都能被指向。
考虑树的情况，我们发现可以构造出一种方案任意n-1个点被指向。
因为题意要求尽量小的物品存在，所以我们规定树中值最大的点不被指（同样在并查集中可以实现，开一个数组标记某个元素被不被指，合并两个并查集时将根较小的标记为true，并把它连到另一个根上；若某条边的两个点在同一个并查集中，将这个并查集的根标为true）。
最后 $O(n)$ 判断一下就可以了。

可拆的并查集

其实就是不加路径压缩…

[BZOJ 1016] 最小生成树计数

[Description]

给出一个n个点m条边的带权无向图，相同边权不会超过10个，询问最小生成树个数。

[Hint]

$n≤100,m≤1000$

[Solution]

每种边权的贡献是一定的。统计一下然后DFS.

带权并查集

[BZOJ 1202] 狡猾的商人

[Description]

长度为n的一个序列，有m条信息(a,b,c)，表示区间[a,b]的和为c。询问所有信息是否有冲突。

[Hint]

多组数据。 $n≤100,m≤1000$ .

[Solution]

另开一个数组记录一下与根之间的距离即可（比较容易就不多说了）。

More
码一些之前做过的，都相对简单。

[BZOJ 1050] 旅行

最小瓶颈生成树。

[BZOJ 1015] 星球大战

离线处理。

[BZOJ 2054] 疯狂的馒头

并查集或链表。

[BZOJ 1370] 团伙

设立虚点。

[BZOJ 4195] NOI2015 程序自动分析

NOI竟然有这种题…

Ural1003 奇偶性

虚点。

NOIP2010 关押罪犯

虚点。

NOI2002 银河英雄传说

带权并查集。

NOI2002 食物链

带权并查集或虚点。

POI 代码等式

POI 可爱的猴子

离线处理。

APOI2011 方格染色

好题~