企业网站优化怎么做/临沂色度广告有限公司

题目链接

题目含义

欧拉欧拉欧拉欧拉欧拉欧拉欧拉

题目分析

只要满足每个节点度数是偶数，并且每个点都连通，那么就一定有欧拉回路

度数在加边就能记录，而连通性用一个并查集就行了

相比其他图论，这真的最简单的了

题目代码

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
typedef long long LL;
const int maxn=1e3+7;
int n,m,a,b,root,f[maxn],cnt[maxn];
bool flag;
int get(int x){if(f[x]==x)return x;else return f[x]=get(f[x]);
}
void join(int x,int y){int fx=get(x),fy=get(y);f[fx]=fy;
}
int main(){while(scanf("%d",&n)){if(n==0)return 0;scanf("%d",&m);for(int i=1;i<=n;i++)f[i]=i;memset(cnt,0,sizeof(cnt));for(int i=1;i<=m;i++){scanf("%d%d",&a,&b);cnt[a]++,cnt[b]++;join(a,b);}flag=true;root=0;for(int i=1;i<=n;i++)if(get(i)==i)root++;for(int i=1;i<=n;i++)if(cnt[i]%2)flag=false;if(flag&&root==1)printf("1\n");else printf("0\n");}
}