讨论 / 并查集
wangwei980516 2011-12-10 04:43:00
点我顶贴 收藏 删除
//并查集模型 题目名称:亲戚relation

#include <stdio.h>

int f[1000]={0},n,m,k,sum=0;

//这里是初始化,非常的重要,数组里面存的是自己数组下标的编号就好了

void init()

{

int i;

for(i=1;i<=n;i++)

f[i]=i;

}

//这是找爹的递归函数,不停的去找爹,只到找到祖宗为止

int getf(int v)

{

if(f[v]==v)

return v;

else

{

//这里是路径压缩,每次在函数返回的时候,顺带把路上遇到的人的祖宗都改为最后找到的祖宗的编号

f[v]=getf(f[v]);

return f[v];

}

}

//这里是合并两子集合的函数,如果需要判断的两个节点,在不同的集合中

//我们就把右边的集合,作为左边集合的子集合,

void merge(int v,int u)

{

int t1,t2;

t1=getf(v);

t2=getf(u);

if( t1!=t2 )

{

f[t1]=t2;//经过路径压缩以后,将f[u]的根的值也赋值为v的祖先f[t1]

}

}

//判断连个点是否在一个集合中,不多说了,你懂的

int query(int v,int u)

{

if(getf(v)==getf(u))

return 1;

else

return 0;

}

//请从此处开始阅读程序,从主函数开始阅读程序是一个好习惯

int main()

{

//freopen("test.in","r",stdin);

//freopen("test.out","w",stdout);

int i,x,y;

scanf("%d %d",&n,&m);

//初始化是必须的

init();

for(i=1;i<=m;i++)

{

//开始集合的合并处理

scanf("%d %d",&x,&y);

merge(x,y);

}

scanf("%d",&k);

for(i=1;i<=k;i++)

{

scanf("%d %d",&x,&y);

//判断他们是否有关系

if(query(x,y))

printf("Yes\n");

else

printf("No\n");

}

return 0;

}

查看更多回复
提交回复