并查集模板

Comments: No Comments
Published on: 2011 年 03 月 23 日

来自Lifeng Wang http://hi.baidu.com/fandywang_jlu

前辈06年写的东西,追随前人足迹继续努力。

//Abstract: UFSet                   
//Author:Lifeng Wang (Fandywang)  
// Model One 与Model 2 路径压缩方式不同,合并标准不同  
const int MAXSIZE = 500010;  
int rank[MAXSIZE];    // 节点高度的上界  
int parent[MAXSIZE]; // 根节点  
int FindSet(int x){// 查找+递归的路径压缩  
    if( x != parent[x] ) parent[x] = FindSet(parent[x]);  
    return parent[x];  
}  
void Union(int root1, int root2){  
    int x = FindSet(root1), y = FindSet(root2);  
    if( x == y ) return ;  
    if( rank[x] > rank[y] ) parent[y] = x;  
    else{  
        parent[x] = y;  
        if( rank[x] == rank[y] ) ++rank[y];  
    }  
}  
void Initi(void){  
    memset(rank, 0, sizeof(rank));  
    for( int i=0; i < MAXSIZE; ++i ) parent[i] = i;  
}  
//Model Two  
const int MAXSIZE = 30001;  
int pre[MAXSIZE]; //根节点i,pre[i] = -num,其中num是该树的节点数目;  
//非根节点j,pre[j] = k,其中k是j的父节点  
int Find(int x){//查找+非递归的路径压缩  
    int p = x;  
    while( pre[p] > 0 )    p = pre[p];  
    while( x != p ){  
        int temp = pre[x]; pre[x] = p; x = temp;  
    }  
    return x;  
}  
void Union(int r1, int r2){  
    int a = Find(r1); int b = Find(r2);  
    if( a == b ) return ;  
    //加权规则合并  
    if( pre[a] < pre[b] ){  
        pre[a] += pre[b]; pre[b] = a;  
    }  
    else {  
        pre[b] += pre[a]; pre[a] = b;  
    }  
}  
void Initi(void)  
{  
    for( int i=0; i < MAXSIZE; ++i ) pre[i] = -1;  
} 

并查集的一些题目和相关解题报告:

POJ 1611 The Suspects 最基础的并查集
POJ 2524 Ubiquitous Religions 最基本的并查集
POJ 1182 食物链 并查集的拓展
注意: 只有一组数据;
要充分利用题意所给条件:有三类动物A,B,C,这三类动物的食物链
构成了有趣的环形。A吃B, B吃C,C吃A。也就是说:只有三个group
POJ 2492 A Bug's Life 并查集的拓展
法一:深度优先遍历
每次遍历记录下该点是男还是女,只有:男-〉女,女-〉男满足,否则,找到同性恋,结束程序。
法二:二分图匹配
法三:并查集的拓展:和1182很像,只不过这里就有两组,而1182是三组,1611无限制
POJ 1861 Network == zju_1542 并查集+自定义排序+贪心求"最小生成树"
答案不唯一,不过在ZOJ上用QSORT()和SORT()都能过,在POJ上只有SORT()才能过...
POJ 1703 Find them, Catch them 并查集的拓展
这个和POJ 2492 A Bug's Life很像,就是把代码稍微修改了一下就AC了!
注意:And of course, at least one of them belongs to Gang Dragon, and the same for Gang Snake. 就是说只有两个组。
POJ 2236 Wireless Network 并查集的应用
需要注意的地方:1、并查集;2、N的范围,可以等于1001;3、从N+1行开始,第一个输入的可以是字符串。
POJ 1988 Cube Stacking 并查集很好的应用
1、与 银河英雄传说==NOI2002 Galaxy一样;2、增加了一个数组behind[x],记录战舰x在列中的相对位置;3、详细解题报告见银河英雄传说。

JOJ 1905 Freckles == POJ 2560 最小生成树

法一:Prim算法;法二:并查集实现Kruskar算法求最小生成树

JOJ 1966 Super Market III == PKU 1456 Supermarket 带限制的作业排序问题(贪心+并查集)

提高题目:
POJ 2912 Rochambeau
POJ 1733 Parity game
POJ 1308 Is It A Tree?

///////////////////////////////////////////////////////////////////////////

补充并查集的另外一种操作:删除操作(来源于2008年杭州赛区题目)

解决方法就是:当删除一个节点时,只需要添加一个节点,以后再出现对该节点的操作时,映射成对新节点的操作(需要一个映射表)

 

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期二, 2017 年 10 月 24 日