解题思路:并查集思想:
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语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:1162 |
C语言程序设计教程(第三版)课后习题6.6 (C++代码)浏览:633 |
回文数字 (C语言代码)浏览:2510 |
C语言程序设计教程(第三版)课后习题10.1 (C语言代码)浏览:567 |
企业奖金发放 (C语言代码)浏览:2325 |
输出九九乘法表 (C语言代码)浏览:1048 |
C语言程序设计教程(第三版)课后习题10.7 (用指针求解)浏览:1477 |
班级人数 (C语言代码)浏览:927 |
C语言程序设计教程(第三版)课后习题8.5 (C语言代码)浏览:668 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:1189 |