Yiner的ACM

成长的痕迹
<2024年11月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

统计

  • 随笔 - 29
  • 文章 - 0
  • 评论 - 2
  • 引用 - 0

常用链接

留言簿(1)

随笔分类

随笔档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜

并查集 HDU1213
#include<iostream>
#include
<stdio.h>
using namespace std;
int sum,n,m;
int father[50001];

void makeset(int x)
{
    
for(int i=1;i<=x;i++)
    
{
        father[i]
=i;
    }

}


int findset(int x)//
{
    
if(x!=father[x])
    
{
        father[x]
=findset(father[x]);
    }
//回溯
    return father[x];
}



void Union(int a,int b)
{
   
int x=findset(a);
   
int y=findset(b);
   
if(x==y)
   
return;
   sum
=sum-1;
   father[y]
=x;
}



int main()
{
    
int l;
  scanf(
"%d",&l);
    
for(int j=1;j<=l;j++)
    
{    scanf("%d%d",&n,&m);
        sum
=n;
        makeset(n);
        
int first,second;
        
for(int i=1;i<=m;i++)
        
{
            scanf(
"%d%d",&first,&second);
            Union(first,second);
        }

        printf(
"%d\n",sum);
        getchar();
    }

    
return 0;
}

posted on 2011-03-30 11:27 Yiner 阅读(490) 评论(0)  编辑 收藏 引用 所属分类: 并查集


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