@DATASOURCE
2015-08-08T11:28:42.000000Z
字数 6276
阅读 1556
数据结构
并查集
并查集是一种用来管理元素分组情况的数据结构。冰茶既可以高效的进行如下操作。不过需要注意并查集虽然可以进行合并操作,但是却无法进行分割操作。 并查集可以查询元素a和元素b是否属于同一组。 并查集可以合并元素a和元素b所在的组。
- 初始化
把每个点所在集合初始化为其自身。
通常来说,这个步骤在每次使用该数据结构时只需要执行一次,无论何种实现方式,时间复杂度均为O(N)。
//代码:
void init(){
int i;
for(i = 0; i < n; i++)
par[i] = i;
}
- 查找
查找元素所在的集合,即根节点。
//代码:
int find(int x){
if(par[x] != x)
par[x] = find(par[x]);
return par[x];
}
注意在这一步中通常采用路径优化,代码中 par[x] = find(par[x]); 即采用了路径优化,做了如图所示的转化,将所有的子节点都直接挂载在根节点上,使得接下来的查找更高效。
- 合并
将两个元素所在的集合合并为一个集合。
通常来说,合并之前,应先判断两个元素是否属于同一集合,这可用上面的“查找”操作实现。
//代码:
void Union(int x, int y){
int fx = find(x);
int fy = find(y);
if(fx != fy)
par[fy] = fx;
}
- 代码说明,先查找两个元素是否属于同一集合,即他们的根节点是否相同,若不相同就合并他们。
这里也可以进一步优化,对于每一个集合所形成的树,用一个rank[N] 数组来记录它的高度,合并时如果两棵树的高度不同,那么从rank 小的向rank 大的连边。
//代码
void Union(int x, int y){
int fx = find(x);
int fy = find(y);
if(fx != fy){
if(rank[fx] >= rank[fy]){
par[fy] = fx;
rank[fx]++;
}
else{
par[fx] = fy;
rank[fy]++;
}
}
}
- 复杂度分析
在增加了路径优化和合并注意高度的优化后,并查集的效率非常高。可以证明,通过这种树形结构实现的带启发式路径压缩的并查集,Find和Union操作的平均代价是O(lgn),这和二分查找的复杂度一致,可以证明这已经是理论上最好的算法了,不可能有更好的算法了。如果不进行这种路经压缩的话,并查集就退化成了链表,在同一链表中的元素属于同一集合,这样的话Find的复杂度是O(n)。
- 题目大意:
有n 个数字,接下来会有m对数字,每一对数字属于同一类。
输入数据包括情况的数目,每一种情况包括有数据n和m,接下来的m行包括了两个数据i和j,表示数字i和j是同一类。数字是从1到n编号的,若n=0并且m=0则表示输入结束 对于每一种情况,显示出这n个数字的种类数。- 思路分析:
并查集的初级题目,可以用根节点的rank存储这一类的元素个数,子节点的rank全置为零,这样只要看有几个rank并不为零就可以确定这n个数字的种类数。
//代码示例:
#include<iostream>
#define N 50005
using namespace std;
int par[N], rank[N]; //par[N] 为 i 的父节点
int n, m;
void init(){ //初始化
int i;
for(i = 1; i <= n; i++){
rank[i] = 1;
par[i] = i;
}
}
int find(int x){ //找根结点
if(par[x] == x)
return x;
else
return par[x] = find(par[x]);
}
void unite(int x, int y){ //合并两个元素,同时,注意rank的处理
x = find(x);
y = find(y);
if(x == y) return ;
if(rank[x] > rank[y]){
rank[y] = 0;
par[y] = x;
rank[x] ++;
}
else if(rank[x] < rank[y]){
par[x] = y;
rank[x] = 0;
rank[y] ++;
}
else{
par[y] = x;
rank[y] = 0;
rank[x] ++;
}
}
int main(){
int i, j, x, y, sum, a = 0;
while(cin >> n >>m){
if(n == 0 && m == 0)
break;
a++;
sum = 0;
init();
for(i = 0; i < m; i++){
cin >> x >> y;
unite(x, y);
}
for(i = 1; i <= n; i++){ //如果rank不为零,则记为一个种类。
if(rank[i] != 0)
sum += 1;
}
cout <<"Case "<< a <<": "<< sum << endl;
}
return 0;
}
题目大意:将所有的数字分为两个部分并由输入的字符来确定要做的事情,其中A 来询问后面两个数的关系,D表示后面的两个数属于不同的类别。
输入的第一行是一个字母t, 代表测试样例数目,每个测试样例的第一行包括两个数,第一个数 n 代表数字的个数(编号1~n),第二个数 m 表示接下来有m 行,每一行包括一个字符’A’或’D’表示之后两个数的关系。
对于每一个输入的’A’,输出两个数的关系,” Not sure yet.”,” In different gangs.”,” In the same gang.”解题思路: 活用rank数组(代码中的rela数组)rank[i] = 0,表示节点 i 与根节点是同一类,rank[i] = 1表示节点 i 与根节点是不同类的。
//示例代码:
#include<iostream>
#include<stdio.h>
#define N 100005
using namespace std;
int par[N], rank[N], rela[N];
int n, m;
void init(){
int i;
for(i = 1; i <= N; i++){
par[i] = i;
rela[i] = 0;
}
}
int find(int x){
if(par[x] == x)
return x;
else{
int temp = par[x];
par[x] = find(par[x]);
rela[x] = (rela[temp] + rela[x]) % 2;
// rela[x] =(rela[temp] ^ rela[x]);
return par[x];
}
}
void unit(int x, int y){
int fx = find(x);
int fy = find(y);
if(fx == fy) return;
else{
par[fy] = fx;
rela[fy] = (rela[x] + 1 -rela[y]) % 2;
//rela[y] = !(rela[x] ^ rela[y]);
}
}
void sol(int x, int y){
if(find(x)== find(y) && rela[x] == rela[y])
printf("In the same gang.\n");
else if(find(y) == find(x) && rela[x] != rela[y])
printf("In different gangs.\n");
else
printf("Not sure yet.\n");
return;
}
int main(){
ios_base::sync_with_stdio(false);
int t, i, n, x, y;
char ch;
scanf("%d",&t);
while(t--){
scanf("%d %d", &n, &m);
init();
for(i = 1; i <= m; i++){
getchar();
scanf("%c %d %d", &ch, &x, &y);
if(ch == 'A')
sol(x, y);
else
unit(x, y);
}
}
return 0;
}
- 网上还有一种很不可思议的解法,我自己也搞不懂为什么会这样,直接上代码了:
#include <cstdio>
#include <iostream>
using namespace std;
int f[200001],n,m,x,y,cas;
char c;
int find(int x) {
if (x!=f[x]) f[x] = find(f[x]);
return f[x];
}
void Union(int x,int y) {
int px = find(x);
int py = find(y);
if (px != py) f[px] = py;
}
int main() {
scanf("%d",&cas);
while (cas--) {
scanf("%d%d",&n,&m);
for (int i=1;i<=2*n;i++) f[i] = i;
for (int i=1;i<=m;i++) {
scanf("%c%c %d %d",&c,&c,&x,&y);
if (c=='D') {
Union(x,y+n);
Union(y,x+n);
}
else {
if (find(x)==find(y)) printf("In the same gang.\n");
else if (find(x)==find(y+n)||find(y)==find(x+n))
printf("In different gangs.\n");
else printf("Not sure yet.\n");
}
}
}
return 0;
}
- 题目大意:(直接上题吧)
动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形。A吃B, B吃C,C吃A。
现有N个动物,以1-N编号。每个动物都是A,B,C中的一种,但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述:
第一种说法是"1 X Y",表示X和Y是同类。
第二种说法是"2 X Y",表示X吃Y。
此人对N个动物,用上述两种说法,一句接一句地说出K句话,这K句话有的是真的,有的是假的。当一句话满足下列三条之一时,这句话就是假话,否则就是真话。
1) 当前的话与前面的某些真的话冲突,就是假话;
2) 当前的话中X或Y比N大,就是假话;
3) 当前的话表示X吃X,就是假话。
你的任务是根据给定的N(1 <= N <= 50,000)和K句话(0 <= K <= 100,000),输出假话的总数。Input
第一行是两个整数N和K,以一个空格分隔。
以下K行每行是三个正整数 D,X,Y,两数之间用一个空格隔开,其中D表示说法的种类。
若D=1,则表示X和Y是同类。
若D=2,则表示X吃Y。Output
只有一个整数,表示假话的数目。Sample Input
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5Sample Output
3
- 解题思路:活用rank数组,rank[i] = 0 表示 i 与par[i] 是同类,rank[i] = 1 表示 i 吃par[i] , rank[i] = 2 表示par[i] 吃 i ;
//代码示例:
#include<cstdio>
#define N 50005
using namespace std;
int par[N], rela[N]; // rela[a] == 0 表示 a 与 par[a] 同类
int n, k, a, b; // rela[a] == 1 表示 a 吃 par[a]
// rela[a] == 2 表示 a 被 par[a] 吃
void init(){ // *******************************************************************
int i; // 若 rela[a] == 0,rela[par[a]] == 0 -> rela[a] == 0;
for(i = 1; i <= n; i++){ // 若 rela[a] == 0, rela[par[a]] == 1 -> rela[a] == 1;
par[i] = i; // 若 rela[a] == 0, rela[par[a]] == 2 -> rela[a] == 2;
rela[i] = 0; // 若 rela[a] == 1, rela[par[a]] == 0 -> rela[a] == 1;
} // 若 rela[a] == 1, rela[par[a]] == 2 -> rela[a] == 0;
} // 若 rela[a] == 2, rela[par[a]] == 0 -> rela[a] == 2;
// 若 rela[a] == 2, rela[par[a]] == 1 -> rela[a] == 0;
int find(int x){ // 若 rela[a] == 2, rela[par[a]] == 2 -> rela[a] == 1;
int y;
if(par[x] == x) // 综合所有情况,可以得出结论 rela[a] = (rela[a] + rela[par[a]]) % 3;
return x;
y = par[x]; // ******************************************************************************
par[x] = find(y);
rela[x] = (rela[x] + rela[y]) % 3;
return par[x]; // 若 d == 1, 若 rela[a] == 0, rela[b] == 0 时,rela[a] == 0;
} // (同类) rela[b] == 1 时,rela[a] == 1;
// rela[b] == 2 时,rela[a] == 2;
void unit(int x, int y, int d){ // 此处的 d 传入的实参为 d - 1; // 若 rela[b] == 0, rela[a] == 0 时,rela[a] == 0;
int fx = find(x); // rela[a] == 1 时,rela[a] == 1;
int fy = find(y); // rela[a] == 2 时,rela[a] == 2;
if(fx == fy) // 若 d == 2, 若 rela[a] == 0, rela[b] == 0 时,rela[a] == 1;
return; // (a 吃 b) rela[b] == 1 时,rela[a] == 2;
else{ // rela[b] == 2 时,rela[a] == 0;
par[fx] = fy; // 若 rela[b] == 0, rela[a] == 0 时,rela[a] == 1;
rela[fx] = (rela[y] - rela[x] + d + 3) % 3; // (注意,此时的a是原a的根节点) rela[a] == 1 时,rela[a] == 0;
} // rela[a] == 2 时,rela[a] == 2;
return; // 综合所有情况,可以得出结论 rela[a] = (rela[b] - rela[a] + d - 1 + 3) % 3;
}
// ***********************************************************************************
int main(){
int i, sum = 0, d, fx, fy;
scanf("%d %d",&n,&k);
init();
for(i = 1; i <= k; i++){
scanf("%d %d %d",&d,&a,&b);
if(a > n || b > n ||(d == 2 && a == b))
sum++; // 真话的条件: 当d == 1(a 与 b 同类)
else{ // a 与 par[a] 同类,即 rela[a] == 0 时,rela[b] == 0;
fx = find(a); // a 吃 par[a], 即 rela[a] == 1 时,rela[b] == 1;
fy = find(b); // a 被 par[a]吃, 即 rela[a] == 2 时,rela[b] == 2;
if(fx == fy && ((rela[a] - rela[b] + 3) % 3 != d - 1)) // 当 d == 2(a 吃 b)
sum++; // a 与 par[a] 同类,即 rela[a] == 0 时,rela[b] == 2;
else unit(a, b, d - 1); // a 吃 par[a], 即 rela[a] == 1 时,rela[b] == 0;
} // a 被 par[a]吃, 即 rela[a] == 2 时,rela[b] == 1;
}
printf("%d\n",sum);
return 0;
}