并查集(模板&典型例题整理)
2024-08-29 10:11:41
参考:https://blog.csdn.net/oliver233/article/details/70162173
带路径压缩模板:
#include<stdio.h>
int father[];
int Find(int x)
{ if(x!=father[x])//注意这里是if不是while!
father[x]=Find(father[x]);
return father[x];
}
void Combine(int a,int b)
{
int fa=Find(a);
int fb=Find(b);
if(fa!=fb)
{
father[fa]=fb;
}
}
int main()
{
// freopen("in.txt","r",stdin);
int n,m;
int i;
int a,b;
while(~scanf("%d",&n))
{
if(n==)
break;
scanf("%d",&m);
int sum=;
for(i=;i<=n;i++)
father[i]=i;
for(i=;i<m;i++)
{
scanf("%d%d",&a,&b);
Combine(a,b);
}
for(i=;i<=n;i++)
{
if(father[i]==i)
sum++;
}
printf("%d\n",sum-);
}
return ;
}
最新文章
- sqlServer去除字段中的中文
- 非root用户的SSH免密登录
- django创建blog
- java字节流与字符流的区别
- (转)qsort和sort
- Python操作Excel
- HDOJ 1590
- snoopy 强大的PHP采集类使用实例代码
- bpel 之伙伴
- 子元素增加margin-top会增加给父元素的问题
- 泛型? extents super
- 传感器 Sensor 加速度【示例】
- codility上的练习(3)
- WebApi HttpMsgHanler的执行顺序
- Django_rest framework 框架介绍
- java eclipse中使用wsdl生成soap 的客户端代码
- Java线程池(待续)
- mysql安装时,提示:Failed to start service MYSQL80
- 标准误(Standard Error)
- Pandas.plot 做图 demo(scatter,bar,pie)