yes you do

yes i do
posts - 4, comments - 2, trackbacks - 0, articles - 0

PKU2492 A Bug's Life(并查集)

Posted on 2009-05-22 17:19 chenweiwei 阅读(294) 评论(0)  编辑 收藏 引用
并查集的简单变种

初始化
初始化的时候增加一个变题用来记录每只虫子的对立面。数组初始化均为-1，标志对立面未找到。

输入
查找两只虫子的对立面是否有记录，哪果有记录则将记录与输入的另一只虫子union，第二只虫子也这样操作。

判断
判断两足虫子是否为同性恋只需要判断他们的祖先是否一相同，如果相同则标记找到，如果不同按照上面的方法操作

想法
这道题最重要的是把同类合并，然后每次输入判断两只虫子是否在张图内，其中的技巧在于每次输入的两足虫子如果符合条件那们他们一定不在同一张图内，因为需要找另外一只虫子把他们加入的自己的那张图中，所以引入了opt这个数组。当然我也是参考了别人的程序，如果真的是实验比赛中恐怕很难想出这个方法。感谢提供了代码的先驱们。

void Init(int nt)//初始化
{
    for (int i=0; i <= nt;i++)
    {
        parent[i] = i;
        rank[i] = 0;
        opt[i]=-1;//表示未找到对立面
    }
}

//判断是否出现同性恋
for(i=0;i<m;i++)
        {
            scanf("%d %d",&a,&b);
            int finda=FindSet(a);
            int findb=FindSet(b);
            if(finda==findb)flag=1;
            else
            {
                if(opt[a]!=-1)
                {
                    UnionSet(opt[a],b);
                }
                if(opt[b]!=-1)
                {
                    UnionSet(opt[b],a);
                }
                opt[a]=b;
                opt[b]=a;
            }

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理