P2097 资料分发

点击查看代码

#include<bits/stdc++.h>using namespace std;const int N=1e5+10;
int n,m,ans;
int p[N];
bool st[N];int find(int x)
{if(p[x]!=x) p[x]=find(p[x]);return p[x];
}int main()
{cin>>n>>m;for(int i=1;i<=n;i++) p[i]=i;int a,b;while(m--){cin>>a>>b;a=find(a),b=find(b);if(a!=b) p[a]=find(b);}for(int i=1;i<=n;i++){int x=find(i);if(st[x]==false){st[x]=true;ans++;}}cout<<ans<<endl;return 0;
}

在模板之上的一次简单运用，增进了对并查集连通属性的理解，如果一些点在同一个集合中，那他们就是连通的，用相当简单的代码和逻辑实现了相当稠密的图 本题就是查找不相互连通块的数量，就是根节点不同的集合数目