解题思路:并查集思想:
1.初始化:每个结点的父亲结点首先设为它本身。
2.路径压缩(解决特殊情况下的树的层次深而造成的复杂度增大的问题)
3.合并
注意事项:1.前期未经过路径压缩的树形结构并查集,树的深度有可能是n。
2.并查集一定要记得初始化。
3.有些并查集的题目用cin,cout有可能会超时。遇到常数比较大的尽量不要用cin,cout输入输出。
参考代码:
#include
using namespace std;
typedef long long ll;
const int N=1e6+10;
ll p[N],m,n,i,t,a,b;
int find(int x)
{
return x==p[x]?x:(p[x]=find(p[x]));
}
int main()
{
cin>>m>>n;
int root=m*n;
for(i=1;i<=root;i++){
p[i]=i;
}
cin>>t;
for(i=0;i<t;i++){
cin>>a>>b;
if(find(a)!=find(b)){
p[find(a)]=find(b);
root--;
}
}
cout<<root<<endl;
return 0;
}
0.0分
1 人评分
C语言训练-阿姆斯特朗数 (C语言代码)浏览:849 |
分糖果 (C++代码)浏览:1438 |
母牛的故事 (C语言代码)浏览:1427 |
图形输出 (C语言代码)浏览:1375 |
DNA (C语言代码)浏览:391 |
整除问题 (C语言代码)浏览:518 |
A+B for Input-Output Practice (IV) (C语言代码)浏览:503 |
C语言训练-斐波纳契数列 (C语言代码)浏览:593 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:446 |
2003年秋浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:1317 |