Yiner的ACM

成长的痕迹
<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

统计

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

常用链接

留言簿(1)

随笔分类

随笔档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜

并查集 HDU1232

 

#include<iostream>
#include
<stdio.h>
#include
<string.h>
using namespace std;

bool flags[1001];
int father[1001];

void makeset(int n)
{
    
for(int i=1;i<=n;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;
        father[y]
=x;
}


int main()
{
    
int n,m;
    
while(scanf("%d %d",&n,&m)!=EOF)
    
{
        memset(flags,
false,sizeof(flags));
        
if(n==0)
        
break;
        makeset(n);
        
int first,second;
        
for(int i=1;i<=m;i++)
         
{
             scanf(
"%d %d",&first,&second);
             Union(first,second);
         }

         
for(int i=1;i<=n;i++)//判断树的棵数
         {
             flags[findset(i)]
=true;
         }

         
int k=0;
         
for(int i=1;i<=n;i++)
         
{
             
if(flags[i]==true)
             k
++;
         }

         printf(
"%d\n",k-1);//需要增加的路数等于树的棵树k-1
    }

        
return 0;
}

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


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