您當(dāng)前位置：首頁 > php開源 > php教程 > HDU 3560 并查集

HDU 3560 并查集

來源：程序員人生發(fā)布時(shí)間：2016-06-30 08:53:04 閱讀次數(shù)：2778次

點(diǎn)擊打開鏈接

題意：給1個(gè)無向圖，問共有多少聯(lián)通塊然后問這些聯(lián)通塊中有幾個(gè)是構(gòu)成1個(gè)環(huán)的，也就是每一個(gè)點(diǎn)的度都為2

思路：判斷聯(lián)通塊直接簡單的并查集就好了，然后對每一個(gè)聯(lián)通塊就算1下里面的所有點(diǎn)的度是否是2就好了，只要有1個(gè)不是2的這個(gè)聯(lián)通塊就不是環(huán)PS：開頭初始化時(shí)若用memset就會超時(shí)

#include #include #include #include#includeusing namespace std; typedef long long ll; typedef unsigned long long ull; const int inf=0x3f3f3f3f; const ll INF=0x3f3f3f3f3f3f3f3fll; const int maxn=100010; int f[maxn],sum[maxn],flag[maxn]; int find1(int x){ if(x!=f[x]) f[x]=find1(f[x]); return f[x]; } void unite(int a,int b){ int aa=find1(a); int bb=find1(b); if(aa==bb) return ; f[aa]=bb; } int main(){ int n,m,u,v; while(scanf("%d%d",&n,&m)!=⑴){ if(n==0&&m==0) break; int ans1=0,ans2=0; for(int i=0;i<=n;i++) f[i]=i,flag[i]=0,sum[i]=0; for(int i=0;i

生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈
程序員人生

------分隔線----------------------------

上一篇 5類系統(tǒng)推薦算法，告訴你用戶需要什么

下一篇 ActiveMQ源碼解析（四）：聊聊消息的可靠傳輸機(jī)制和事務(wù)控制

分享到:

------分隔線----------------------------

為碼而活

積分：4237

15粉絲

7關(guān)注

欄目熱點(diǎn)

日本搞逼视频_黄色一级片免费在线观看_色99久久_性明星video另类hd_欧美77_综合在线视频

HDU 3560 并查集