九度：题目1027：欧拉回路 - c++编程基础

题目描述：

欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个图，问是否存在欧拉回路？

输入：

测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是节点数N ( 1 < N < 1000 )和边数M；随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个节点的编号（节点从1到N编号）。当N为0时输入结束。

输出：

每个测试用例的输出占一行，若欧拉回路存在则输出1，否则输出0。

样例输入：

样例输出：

1
0

分析：

一上来我直接用递归暴搜，结果超时：

#include 
            
             
#include 
             
               #include 
              
                #define MAX 1005 int N,M; int a,b; int map[MAX][MAX]; bool vis[MAX]; bool dfs(int k,int n){ if(n==N){ if(map[k][a])return true; else return false; } for(int i=1;i<=N;i++){ if(map[k][i]&&!vis[i]){ vis[i]=true; if(dfs(i,n+1))return true; vis[i]=false; } } return false; } int main(){ //freopen("C:\\in.txt","r",stdin); while(~scanf("%d",&N)&&N){ scanf("%d",&M); memset(map,0,sizeof(map)); memset(vis,0,sizeof(vis)); for(int i=0;i
               
                
 所以，得从欧拉回路的性质出发，
                 
                1、欧拉回路必须能从1一直能连线到n的连通图，所以用并查集的话，就只能有1个集合 
                2、欧拉回路： 
                有向图：所有的顶点出度=入度。





 
                无向图：所有顶点都是偶数度。 
                满足上面两个条件的话就一定是欧拉回路 
                所以，利用并查集和节点度数的奇偶判断就可知是否是欧拉回路 
                
                /*
题目1027：欧拉回路
 
*/
#include 
                 
                  
#include 
                  
                    using namespace std; #define MAX 1005 int N,M; int a,b; int field[MAX]; int degree[MAX]; int find(int x) { if(field[x]==0) return x; field[x] = find(field[x]); return field[x]; } void make(int x,int y)//将x与y合并 { int f1=find(x); int f2=find(y); if(f1!=f2) field[f2]=f1; } int main() { //freopen("C:\\in.txt","r",stdin); while(cin>>N&&N) { cin>>M; memset(field,0,sizeof(field)); memset(degree,0,sizeof(degree)); while(M--) { cin>>a>>b; ++degree[a]; //a的度（出度）++ ++degree[b]; //b的度（入度）++ make(a,b);//将a b合并 } int cnt = 0; //集合的个数，等于1才满足欧拉回路 int flag = 1; for(int i=1;i<=N;++i) { if(field[i]==0) cnt++; if(degree[i]%2==1) flag=0; } if(cnt!=1) flag=0; cout<