加边的无向图--并查集
程序员文章站
2022-03-25 18:55:57
加边的无向图 知识点:并查集 题意:题意简单,给你n个点,m条边,要你求至少要在这个的基础上加多少条无向边使得任意两个点可达。 题解:并查集裸题,直接套用模板即可。 代码: #include #include #include #defin ......
知识点:并查集
题意:题意简单,给你n个点,m条边,要你求至少要在这个的基础上加多少条无向边使得任意两个点可达。
题解:并查集裸题,直接套用模板即可。
代码:
#include<iostream> #include<cstring> #include<algorithm> #define ll long long using namespace std; ll father[1000010]; void init(){//初始化 for(ll i=1;i<=1000010;i++){ father[i]=i; } } ll find (int x){//寻找父节点 if(x==father[x]){ return x; }else{ return father[x]=find(father[x]); } } void merge(int x,int y){ ll p=find(x); ll q=find(y); if(p!=q){/*两个不是一个父节点*/ father[p]=q; } } int main(){ ll n,m; cin>>n/*点*/>>m/*边*/; ll ri,rj; init(); for(ll i=0;i<m;i++){ cin>>ri>>rj; merge(ri,rj); } ll cnt=-1; for(ll i=1;i<=n;i++){ if(i==father[i]){ cnt++; } } printf("%lld",cnt); return 0; }
相同类型的题目推荐:hdu、hdu