技术标签： 图论
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1232
题目大意：已知n个村庄之间有若干条通路，求出使他们联通所需添加的最少道理数。
分析：并查集记录已经联通的村庄集合，集合内部已经联通，m个集合之间需要添加m-1条道路来联通。
实现代码如下：
#include <cstdio>
#include <iostream>
using namespace std;
const int maxn=1000;
int par[maxn];
void init(int n)
{
for(int i=1;i<=n;i++)
par[i]=i;
}
int find(int x)
{
while(par[x]!=x)
x=par[x];
return x;
}
void combine(int a,int b)
{
int fa=find(a);
int fb=find(b);
if(fa!=fb)
par[fa]=fb;
}
int main()
{
int n,m;
while(cin>>n&&n)
{
init(n);
cin>>m;
int a,b;
for(int i=0;i<m;i++)
{
cin>>a>>b;
combine(a,b);
}
int ans=0;
for(int i=1;i<=n;i++)
if(par[i]==i) ans++;
cout<<ans-1<<endl;
}
return 0;
}
文章浏览阅读742次。100兆宽带的网速通常指的是每秒可以传输的数据量为100兆比特（Mb）。在此情况下，1兆比特（Mb）等于100万比特（Mbps），而1字节（B）等于8比特（bps）。因此，100兆宽带的网速可以计算如下：100兆比特/秒=100/8 兆字节/秒= 12.5兆字节/秒所以，100兆宽带的网速约为12.5MBps（兆字节/秒），也可以说为100Mbps（兆比特/秒）。但是需要注意的是，实际的下载和上传速度可能受到各种因素的影响，如网络拥堵、设备性能等。因此，实际使用中您可能会感受到较低的速度。_100m的宽带网速是多少兆
文章浏览阅读2.4w次，点赞13次，收藏44次。Windows 7 通用 CDC 串口驱动程序Windows 7 自带 CDC 串口类设备的驱动程序文件 usbser.sys，所缺的是驱动配置文件 usbser.inf 文件，将 Windows 10 的 usbser.inf 文件拷贝到 Windows 7，注释掉 SourceDisksNames 和 SourceDisksFiles 部分就可以作为 Windows 7 的 CDC 串口类..._cdcserial驱动 win7
文章浏览阅读2.5k次，点赞53次，收藏51次。NLP-词表示_nlp中词语的表示
文章浏览阅读2.4k次。sed -i 's/[ ][ ]*/ /g' file.txt _sed 多个空格替换为1个
文章浏览阅读125次。1. 创建maven聚合工程，结构如下：2. 父工程pom.xml文件<?xml version="1.0" encoding="UTF-8"?><project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 ht_springboot dubbo整合日志
文章浏览阅读1.6k次。Android中视图动画使用率越来越少了，很多大神都使用属性动画了。但个人觉得视图动画比属性动画使用起来更简单，所以能用视图动画实现的就不考虑用属性动画。 今天在项目中使用视图动画时，遇到了几个坑，记录下来，供踩到同样坑的同学参考一下~一、平移与缩放冲突 使用视图动画，常使用到动画集合AnimationSet，然后在动画集合中添加平移、绽放，旋转等动画。_android view有动画时执行invisible
IEEE协会是一个专注于航空与电子系统领域的组织，注册IEEE会员可以享受许多权益，包括免费访问协会资源中心和参加各种会议及活动。
文章浏览阅读774次，点赞20次，收藏14次。除了简历做到位，面试题也必不可少，整理了些题目，前面有117道汇总的面试到的题目，后面包括了HTML、CSS、JS、ES6、vue、微信小程序、项目类问题、笔试编程类题等专题。CodeChina开源项目：【大厂前端面试题解析+核心总结学习笔记+真实项目实战+最新讲解视频】
文章浏览阅读3.9k次。var arr = [12,31,42,54,65,12,31,12,42,22];//统计个数var arr2 = {};arr.forEach(function(item){ if(arr2[item]){ arr2[item] += 1; }else{ arr2[item] = 1; }})console.log(arr2);_统计数组中每个数字出现的次数
文章浏览阅读97次。基于verilog驱动M25P16(FLASH) -------- SPI简介_m25p16 verilog sim model
文章浏览阅读23次。新建hyperv.bat，输入以下内容。管理员运行bat即可。
文章浏览阅读4.9w次。背景前两天写了一篇文章 OSX MAMP 如何为 PHP 5.6 安装 MSSQL 扩展，讲的是自己的个人电脑，也就是开发环境如何为 PHP 5.6 安装 MSSQL 扩展，现在要上生产了，继续讲讲怎么给 CentOS7 安装 PHP - MSSQL 扩展。运行环境操作系统CentOS Linux release 7.8.2003 (Core)集成环境宝塔PHP 5.6.40步骤和之前一样，我们先来整理一下整体的步骤：1、安装 freetds2、安装 mssql.so 扩展（p_宝塔面板centos7/php5.6安装mssql扩展