HDU 3560 并查集

发布时间：2020-12-13 21:09:38 所属栏目：PHP教程来源：网络整理

导读：点击打开链接题意：给1个无向图，问共有多少联通块然后问这些联通块中有几个是构成1个环的，也就是每一个点的度都为2 思路：判断联通块直接简单的并查集就好了，然后对每一个联通块就算1下里面的所有点的度是否是2就好了，只要有1个不是2的这个联通块就不是

点击打开链接

题意：给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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!