题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=1232
畅通工程
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 65589 Accepted Submission(s): 35027
注意:两个城市之间可以有多条道路相通,也就是说
3 3
1 2
1 2
2 1
这种输入也是合法的
当N为0时,输入结束,该用例不被处理。
Hint
Huge input, scanf is recommended.
#include<bits/stdc++.h>
using namespace std;
#define max_v 1005
int pa[max_v];
int rk[max_v];
int ans;
void make_set(int x)
{
pa[x]=x;
rk[x]=0;
}
int find_set(int x)
{
if(x!=pa[x])
pa[x]=find_set(pa[x]);
return pa[x];
}
void union_set(int x,int y)
{
x=find_set(x);
y=find_set(y);
if(x==y)
return ;
ans--;
if(rk[x]>rk[y])
pa[y]=x;
else
{
pa[x]=y;
if(rk[x]>=rk[y])
rk[y]++;
}
}
int main()
{
int n,m;
while(~scanf("%d",&n))
{
if(n==0)
break;
scanf("%d",&m);
for(int i=1;i<=n;i++)
make_set(i);
ans=n-1;
for(int i=0;i<m;i++)
{
int x,y;
scanf("%d %d",&x,&y);
union_set(x,y);
}
printf("%d\n",ans);
}
return 0;
}
HDU 1232 畅通工程(道路连接)(裸并查集)的更多相关文章
-
hdu 1232 畅通工程(并查集算法)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1232 畅通工程 Time Limit: 4000/2000 MS (Java/Others) M ...
-
HDU 1232(畅通工程)题解
以防万一,题目原文和链接均附在文末.那么先是题目分析: [一句话题意] 给定一具有N个节点的图和其边集,求其集合数量. [题目分析] 并查集经典题...其实就是创建好并查集就行了.. [算法流程] 于 ...
-
HDU 1232 畅通工程(模板——并查集)
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1232 Problem Description 某省调查城镇交通状况,得到现有城镇道路统计表,表中列出 ...
-
HDU - 1232 畅通工程-并查集模板
某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇.省*“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可). ...
-
题解报告:hdu 1232 畅通工程(并查集)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1232 Problem Description 某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了 ...
-
HDU - 1232 畅通工程
Problem Description 某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇.省*“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道 ...
-
HDU 1232 畅通工程(并查集)
畅通工程 Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Problem Des ...
-
hdu 1232 畅通工程 解题报告
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1232 并查集入门题.最近在学并查集,它无非包括三个操作:make_set(x).union_set(x ...
-
hdu 1232畅通工程
Problem Description 某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇.省*"畅通工程"的目标是使全省任何两个城镇间都可以实现交通 ...
随机推荐
-
DataSet客户端分页实现
window.$ClientPageHelper=function(fromDs,toDs){ var pageSize=toDs.get('pageSize'); var elist=fromDs. ...
-
ajax传输 基础一
一个简单页面的传输 index.php <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" &quo ...
-
cocos2d-x使用AssetsManager类实现资源的在线更新
从2.1.2版本开始,2dx在libExtensions下添加了一个AssetsManager类用于资源的在线更新和简单的版本管理,同时添加了AssetsManagerTest项目示范了AssetsM ...
-
ASP.NET MVC 快速开发框架之 SqlSugar+SyntacticSugar+JQWidgetsSugar+jqwidgets
jqwidgets.js: 是一个功能完整的框架,它具有专业的可触摸的jQuery插件.主题.输入验证.拖放插件.数据适配器,内置WAI-ARIA(无障碍网页应用)可访问性.国际化和MVVM模式支持. ...
-
AES对称加密算法原理
原著:James McCaffrey 翻译:小刀人 原文出处:MSDN Magazine November 2003 (Encrypt It) 本文的代码下载:msdnmag200311AES.exe ...
-
DBImg: 图片文件-二进制文件的转换
using System; using System.IO; using System.Drawing; //using System.Collections.Generic; //using Sys ...
-
B树在数据库索引中的应用剖析
引言 关于数据库索引,google一个oracle index,mysql index总 有大量的结果,其中很多的使用方法推荐,**索引之n条经典建议云云.笔者认为,较之借鉴,在搞清楚了自己的需求的基 ...
-
ios 设置label的高度随着内容的变化而变化
好吧 步骤1:创建label _GeRenJianJie = [[UILabel alloc]init]; 步骤2:设置label _GeRenJianJie.textColor = RGBAColo ...
-
安装centos mini版,无法联网,用yum安装软件提示 cannot find a valid baseurl for repo:base/7/x86_64 的解决方法
*无法联网的明显表现会有: cannot find a valid baseurl for repo:base/7/x86_64 1.yum install出现 Error: cannot find ...
-
folat i = 0.1; 警告
今天的用途 float i = 0.1;那么编译器警告实际: #include <iostream> using namespace std; int main() { float k ...