1. 两类类别
并查集中有两类类别,即并查集中元素要么属于集合A,要么属于B,且A与B不相交。
利用向量得到关系:
1.1 POJ 2492
源代码:
#include "stdio.h"
int parent[2000],relation[2000];
int find(int x)
{
int root,tail,temp;
if(parent[x]==x)
return x;
else
{
for(root=x;parent[root]!=root;root=parent[root]);
for(tail=x;tail!=root;)
{
temp=parent[tail];
parent[tail]=root;
tail=temp;
}
return root;
}
}
void update(int yroot,int n)
{
int i;
for(i=1;i<=n;i++)
{
if(i!=yroot&&find(i)==yroot)
relation[i]=(relation[i]+relation[yroot])%2;
}
}
void root_union(int x,int y,int xroot,int yroot,int n)
{
relation[yroot]=(relation[x]-relation[y]+1)%2;
update(yroot,n);
parent[yroot]=xroot;
}
int main()
{
int scena_num,bug_num,intera_num,a,b,i,count;
int aroot,broot,suspi_flag;
scanf("%d",&scena_num);
for(count=1;count<=scena_num;count++)
{
scanf("%d%d",&bug_num,&intera_num);
suspi_flag=0;
for(i=1;i<=bug_num;i++)
{
parent[i]=i;
relation[i]=0;
}
while(intera_num--)
{
scanf("%d%d",&a,&b);
aroot=find(a);
broot=find(b);
if(aroot!=broot)
{
root_union(a,b,aroot,broot,bug_num);
}
else
{
if(relation[a]!=(relation[b]+1)%2)
suspi_flag=1;
}
}
if(suspi_flag==1)
printf("Scenario #%d:\nSuspicious bugs found!\n\n",count);
else
printf("Scenario #%d:\nNo suspicious bugs found!\n\n",count);
}
return 0;
}
1.2 POJ 1703
源代码:
#include "stdio.h"
int parent[100000],relation[100000];
int find(int x) //寻找root结点,并更新parent链域的relation值
{
int temp;
if(parent[x]==x)
return x;
temp=parent[x];
parent[x]=find(parent[x]);
relation[x]=(relation[x]+relation[temp])%2;
return parent[x];
}
int main()
{
int T,N,M,i,a,b;
int aroot,broot;
char message;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&N,&M);
for(i=1;i<=N;i++)
{
parent[i]=i;
relation[i]=0;
}
while(M--)
{
getchar();
scanf("%c%d%d",&message,&a,&b);
aroot=find(a);
broot=find(b);
if(message=='A')
{
if(N==2&&a!=b)
printf("In different gangs.\n");
else
{
if(aroot==broot)
{
if(relation[a]==relation[b])
printf("In the same gang.\n");
else
printf("In different gangs.\n");
}
else
printf("Not sure yet.\n");
}
}
else
{
if(aroot!=broot)
{
parent[broot]=aroot;
relation[broot]=(relation[a]-relation[b]+1)%2;
}
}
}
}
return 0;
}
2. 三类类别
并查集中元素属于互不相交的集合A, B, C。
类似地,可以得到如下关系:
r[y]=(r[x]+d)%3 //不能得到r[x]=(r[y]+d)%3
r[yroot]=(r[x]-r[y]+d+3)%3 //+3,是因为r[x]-r[y]+d有可能为负数
其中,0表示与root节点同类,1表示吃root节点,2表示被root节点吃。
2.1POJ 1182
源代码:
#include "stdio.h"
int parent[50000],relation[50000];
int find(int x)
{
int temp;
if(parent[x]==x)
return x;
temp=parent[x];
parent[x]=find(parent[x]);
relation[x]=(relation[x]+relation[temp])%3;
return parent[x];
}
int main()
{
int num_ani,num_sta,i,statement,count=0;
int a,b,aroot,broot,d;
scanf("%d%d",&num_ani,&num_sta);
for(i=1;i<=num_ani;i++)
{
parent[i]=i;
relation[i]=0;
}
while(num_sta--)
{
getchar();
scanf("%d%d%d",&statement,&a,&b);
d=statement-1;
if(a>num_ani||b>num_ani)
count++;
else
{
aroot=find(a);
broot=find(b);
if(aroot!=broot)
{
parent[broot]=aroot;
relation[broot]=(relation[a]-relation[b]+d+3)%3;
}
else if(relation[b]!=(relation[a]+d)%3||(d==1&&a==b))
count++;
}
}
printf("%d\n",count);
return 0;
}
分享到:
相关推荐
数据结构 并查集 查询 快速 实用 ACM
算法与数据结构:并查集实现的方法,以及ACM并查集的一些例子
数据结构并查集基础.ppt
并查集实现,带路径压缩和template,高效查找神器!注:库里面如果没有unordered_map,可以换成hash_map或者map
并查集,在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合...并查集是一种树型的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。常常在使用中以森林来表示。
ACM-数据结构-并查集学习
深入理解并查集算法,细致讲解,专业老师,一步到位 。
并查集 数据结构 优化 复习算法用,附带一个测试用例
数据结构并查集的相关资料,包括几篇并查集的论文,还有POJ上面几道关于并查集的题目的源代码
并查集是一种树型的数据结构,用于处理一些不相交集合的合并问题。 并查集的主要操作有 1-合并两个不相交集合 2-判断两个元素是否属于同一个集合 3-路径压缩
.net 并查集算法例子,简单的一个食物链程序,随便写了写,练习用的。
对高级数据有很详细的解说,是一个很好的学习高级数据结构的资料,内容很好理解,推荐
但是实际上有着更高效的数据结构来判断节点间是否具有连通性,那就是并查集接口并查集这一数据结构由数组构建而成,使用数组下标来表示具体的节点,使用数组保存的值来表示
在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一...即使在空间上勉强通过,运行的时间复杂度也极高,根本就不可能在比赛规定的运行时间(1~3秒)内计算出试题需要的结果,只能用并查集来描述。
本文是对严蔚敏《数据结构(c 语言版)习题集》一书 和严蔚敏《数据结构(c 语言版)习题集中所有算法
并查集是一种树型的数据结构,用于处理一些不相交集合的合并问题。 并查集的主要操作有 1-合并两个不相交集合 2-判断两个元素是否属于同一个集合 3-路径压缩
并查集、树状数组、线段数三种高级数据结构的PPT,以及一些论文
2、并查集合并时高度高的树的根做为新的根 并查集合并时将高度较高的树的根节点作为新树的根节点生成新树,合并后可以减少新 树的高度,提高 find 时的效率。 3、find 用折叠规则来实现并查集 使用折叠规则完成一...
并查集(Union-Find Set): 一种用于管理分组的数据结构。它具备两个操作:(1)查询元素a和元素b是否为同一组 (2) 将元素a和b合并为同一组。 注意:并查集不能将在同一组的元素拆分为两组。 并查集的实现: 用树来实现...
数据结构、算法相关的资源 数据结构、算法相关的资源 数据结构、算法相关的资源 数据结构、算法相关的资源 数据结构、算法相关的资源 数据结构、算法相关的资源 数据结构、算法相关的资源 数据结构、算法相关的资源 ...