题目链接：?pid=1878
【概念】
欧拉回路：若图G中存在这样一条路径，使得它恰通过G中每条边一次,则称该路径为欧拉路径。若该路径是一个圈，则称为欧拉(Euler)回路。
该题目是无向图：
无向图存在欧拉回路的充要条件
一个无向图存在欧拉回路，当且仅当该图所有顶点度数都为偶数,且该图是连通图。
度的概念用这个图来说吧：
a,b,c,d,e的度为3，f的度为5；也就是从该点引出的边有几条，就为几度
奇数条边为奇度，偶数条边为偶度；上图的顶点度数全为奇度，所以不存在欧拉回路，，也就是不能“一笔画”。
判断是否联通用并查集判断即可；
【代码】
#include <iostream>#include <cstring>#include <cstdio>using namespace std;int degree[1200];int n,m;int num[1200];void connect(int a,int b){//并查集<span style="font-family:Arial;">连接</span>if(num[a]==num[b])return ;int p=num[a];int q=num[b];for(int i=1;i<=n;i++){if(num[i]=p)num[i]=q;}}int main(){while(cin>>n&&n){cin>>m;for(int i=1;i<=n;i++)//<span style="font-family:Arial;">并查集的初始化</span>num[i]=i;memset(degree,0,sizeof(degree));for(int i=0;i<m;i++){int a,b;scanf("%d%d",&a,&b);degree[a]++;//度<span style="font-family:Arial;">加1</span>degree[b]++;connect(a,b);} int sign=0;<span style="font-family:Arial;">//用来标记是否所有度数为偶数</span>for(int i=1;i<=n;i++){if(degree[i]%2){sign=1;break;}}if(sign) cout<<"0"<<endl;else{int cnt=0;for(int i=1;i<=n;i++)//<span style="font-family:Arial;">判断是否联通</span>{if(num[i]==i)cnt++;}if(cnt==1)cout<<"1"<<endl;elsecout<<"0"<<endl;}}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
别为荒漠的艰难而哭泣，只为奔流入海功成名就那一天，
