poj 1611 （并查集）

43 阅读 0 评论 29 点赞

我是靠谱客的博主如意春天，最近开发中收集的这篇文章主要介绍poj 1611 （并查集），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

什么是并查集？并查集是一种树型的数据结构。用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。

并查集一般就三个操作：初始化，查找，合并。
一般都是用一个一维数组来组织，数组所存内容为该下标表示点的父节点(实际是一棵树，每个结点都指向父节点，用根节点来标志集合)。

1,初始化函数一般没有什么变化，都是将每个结点的父节点初始化为本身；

2,查找函数一般都是递归的寻找父节点直至根结点，返回根结点的值来标识集合；
并查集的优化，路径压缩
寻找祖先时我们一般采用递归查找，但是当元素很多亦或是整棵树变为一条链时，每次find(x)都是O(n)的复杂度，有没有办法减小这个复杂度呢？
答案是肯定的，这就是路径压缩，即当我们经过"递推"找到祖先节点后，"回溯"的时候顺便将它的子孙节点都直接指向祖先，这样以后再次find(x)时复杂度就变成O(1)了，如下图所示；可见，路径压缩方便了以后的查找。

3,合并函数一般就将两个集合中一个根结点的父节点设为另一个根结点(由这一步使得各个元素合并为一棵树，一开始只是自己指向自己)。

优化：按秩合并，秩，即树的高度。
即合并的时候将元素少的集合合并到元素多的集合中，这样合并之后树的高度会相对较小。

#define MAXN 100005
int n,m,k,fa[MAXN];
int rank[MAXN];
void init(int n)//初始化
{
    for(int i=0;i<=n;i++)
    {
        fa[i]=i;//将每个结点的父节点初始化为本身	
        rank[i]=0;
    }
}
//查找的时候，进行路径压缩fa[x]=find(fa[x])
//把查找路径上的结点都指向根结点，减少树的高度。
int find(int x)
{
   if(x != fa[x])		//一直找到根节点，因为根节点是自己指向自己，x==fa[x]
        fa[x]=find(fa[x]); 	// 递归查找x元素所在的集合,回溯时压缩路径
    return fa[x]; 		//回溯的时候把根节点的值返回给每一个节点。
}
//按秩合并
void unio(int x,int y)
{
   x=find(x);
   y=find(y);
    if(x==y) return ;
    if(rank[y]<rank[x])//将rank值小的合并到大的中
        fa[y]=x;
    else
    {
        fa[x]=y;
        if(rank[x]==rank[y])
            rank[y]++;
    }
}
//不按秩合并

void unio(int x,int y)
{
        x=find(x);
	y=find(y);
    if(x==y) return ;
    fa[y]=x;
}

poj 2492

找出虫子中的gay or Lesbian。。。

题目大意：
输入一个数t，表示测试组数。然后每组第一行两个数字n,m，n表示有n只昆虫，编号从1—n,m表示下面要输入m行交配情况，每行两个整数，表示这两个编号的昆虫为异性，要交配。要求统计交配过程中是否出现冲突，即是否有两个同性的昆虫发生交配。
[输入输出]: [样例]:
SampleInput

2 （二次测试）
3 3(三条虫子，三对信息）
1 2
2 3
1 3
（四条虫子,二对信息)

4 2

1 2
3 4

思路：创建一个数组，存放虫子的伴侣，如果一个虫子的伴侣同样也是另一个虫子的伴侣，那么把这个两个同性虫子就放入到一个集合。

如果下次输入的虫子都是在一个集合中的。那么这俩就是 gay or Lesbian。。。

#include<stdio.h>
const int Max = 2005;
//parent数组存放同一个集合的元素，opp数组存放是一对，（下标和内容对应表示一对）
int n, m;
int parent[Max], opp[Max];

void make_set()
{
    for(int x = 1; x <= n; x ++)
	{
        parent[x] = x;
        opp[x] = 0;
    }
}

int find_set(int x)
{
    if(x != parent[x])  //一直找到根节点，因为根节点是自己指向自己
        parent[x] = find_set(parent[x]);
    return parent[x];
}

void union_set(int x, int y)//把同性的放在一个集合。
{
    x = find_set(x);
    y = find_set(y);
    if(x == y)
	return;
    parent[y] = x;
}

int main()
{
    int t, i, x, y;
    scanf("%d", &t);
    for(i = 1; i <= t; i ++)
	{
        scanf("%d %d", &n, &m);
        make_set();
        bool flag = false;
        while(m--)
	{
            scanf("%d %d", &x, &y);
            if(flag) 
		continue;
            if(find_set(x) == find_set(y))
	    {  // 若x，y同在一个集合，则证明是同性的，有可能是同性恋。
                flag = true;
            }
            if(opp[x] == 0 && opp[y] == 0)
	   {
                opp[x] = y;//表明y是x的异性
                opp[y] = x;
            }
            else if(opp[x] == 0)
	   {
                opp[x] = y;  //y有对应的一对，但是现在 x也和y配一对了，那么y的另一对和x就是同性的。
                union_set(x, opp[y]);
            }
            else if(opp[y] == 0)
	   {
                opp[y] = x;
                union_set(y, opp[x]);
            }
            else
	   {
                union_set(x, opp[y]);
                union_set(y, opp[x]);
            }
        }
        printf("Scenario #%d:n", i);
        if(flag) 
			printf("Suspicious bugs found!nn");
        else 
			printf("No suspicious bugs found!nn");
    }
    return 0;
}

执行分析：

输入1 2

opp[2] = 1//1和2为一对

opp[1] =2

输入2 3

opp[3] = 2//2 和3为一对

这时x=2，2 已经有另一半了是 1，而3的另一半是 2，说明1和3是同性，他俩的对象都是x为2，合并到一个集合中去。

parent数组这时候的值：0 3 2 3 即下标为1处的值为3，也即是元素1 指向了根节点 3（数组的下标）

输入 1 3

find_set();返回其根节点都是 3，在一个集合中，是同性恋。

。。。。

整合资料来源;http://cavenkaka.iteye.com/blog/1171373