欧拉回路
欧拉回路：图G，若存在一条路，经过G中每条边有且仅有一次，称这条路为欧拉路，如果存在一条回路经过G每条边有且仅有一次，
称这条回路为欧拉回路。具有欧拉回路的图成为欧拉图。
判断欧拉路是否存在的方法
有向图：图连通，有一个顶点出度大入度1，有一个顶点入度大出度1，其余都是出度=入度。
无向图：图连通，只有两个顶点是奇数度，其余都是偶数度的。
判断欧拉回路是否存在的方法
有向图：图连通，所有的顶点出度=入度。
无向图：图连通，所有顶点都是偶数度。
程序实现一般是如下过程：
1.利用并查集判断图是否连通，即判断可以作为起点的点的个数，如果大于1，说明不连通。
2.根据出度入度个数，判断是否满足要求。
3.利用dfs输出路径。
Notice:并查集使用中连接点时必须判断两点是否不在一个集合，不然可能会造成STACK_OVERFLOW的错误，下面做的这个就是血淋淋的例子啊！
1 #include<iostream> 2 using namespace std; 3 int n,m,cnt; 4 int *p,*degree,*odd,*vis,*record; 5 void init(int g) 6 { 7 p=new int[g+1]; 8 degree=new int[g+1]; 9 odd=new int[g+1]; 10 vis=new int[g+1]; 11 record=new int[g+1]; 12 cnt=0; 13 for(int i=0;i<=g;i++) 14 { 15 p[i]=-1; 16 degree[i]=0; 17 odd[i]=0; 18 vis[i]=0; 19 } 20 } 21 void destroy() 22 { 23 delete []p; 24 delete []degree; 25 delete []odd; 26 delete []vis; 27 delete []record; 28 } 29 int find(int x) 30 { 31 if(p[x]<0)return x; 32 return p[x]=find(p[x]); 33 } 34 void Union(int a,int b) 35 { 36 int fa=find(a); 37 int fb=find(b); 38 if(fa==fb)return;//这一步判断很重要，在这里错了好多次，其他地方没错； 39 int da=p[fa]; 40 int db=p[fb]; 41 if(da>db) 42 { 43 p[fa]=fb; 44 p[fb]+=da; 45 } 46 else 47 { 48 p[fb]=fa; 49 p[fa]+=db; 50 } 51 } 52 int main() 53 { 54 int a,b; 55 while(scanf("%d %d",&n,&m)==2) 56 { 57 init(n); 58 for(int i=1;i<=m;i++) 59 { 60 scanf("%d %d",&a,&b); 61 degree[a]++; 62 degree[b]++; 63 Union(a,b); 64 } 65 int f; 66 for(int i=1;i<=n;i++) 67 { 68 f=find(i); 69 if(!vis[f]) 70 { 71 vis[f]=1; 72 record[cnt++]=f; 73 } 74 if(degree[i]%2==1) 75 odd[f]++; 76 } 77 int res=0; 78 for(int i=0;i<cnt;i++) 79 { 80 if(degree[record[i]]==0)continue; 81 if(odd[record[i]]==0) 82 res++; 83 else res+=odd[record[i]]/2; 84 } 85 destroy(); 86 printf("%d ",res); 87 } 88 return 0; 89 }