HDU 3560 并查集
來源：程序員人生 發布時間：2016-06-30 08:53:04 閱讀次數：2768次
點擊打開鏈接
題意：給1個無向圖，問共有多少聯通塊然后問這些聯通塊中有幾個是構成1個環的，也就是每一個點的度都為2
思路：判斷聯通塊直接簡單的并查集就好了，然后對每一個聯通塊就算1下里面的所有點的度是否是2就好了，只要有1個不是2的這個聯通塊就不是環PS： 開頭初始化時若用memset就會超時
#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
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
