HDU 3560 并查集
来源：程序员人生 发布时间：2016-06-30 08:53:04 阅读次数：2577次
点击打开链接
题意：给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
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
