加邊的無向圖
知識點：并查集
題意：題意簡單，給你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; }
相同型別的題目推薦：HDU1863、HDU1232
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/40792.html
標籤：C++
上一篇：2020年04月10日UCF Local Programming Contest 2017
下一篇：翻轉字串里面的單詞