无向图欧拉回路，判断

题：欧拉回路

本题是给图判断图中是否存在欧拉回路，欧拉回路的含义题目中也说明了，本题的思路就是并查集判断图是否连通，如果不连通不可能存在欧拉回路，如果连通了判断欧拉回路存在的条件是图中各点的度全部为偶数（所以这里需要注意将存放顶点度的数组初始化）。

 1 /***********************************************/
 2 int in[maxn],out[maxn];
 3 int st[maxn];
 4 
 5 int find(int r)
 6 {
 7     while(st[r]!=r)
 8         r=st[r];
 9     return r;
10 }
11 
12 void add(int a,int b)
13 {
14     int fa=find(a);
15     int fb=find(b);
16     if(fa<fb) st[fb]=fa;
17     else st[fa]=fb;
18 }
19 
20 int mp[maxn];
21 
22 int main()
23 {
24     int n,m;
25     while(cin>>n && n)
26     {
27         cin>>m;
28         mem0(st);
29         mem0(mp);
30         mem0(in);
31         for(int i=1;i<=n;i++) st[i]=i;
32         for(int i=1;i<=m;i++)
33         {
34             int a,b;
35             cin>>a>>b;
36             if(a>b) swap(a,b);
37             if(mp[a]!=b)
38             {//输入的边不重复 
39                 mp[a]=b;
40                 in[a]++;
41                 in[b]++;
42                 add(a,b);//合并 
43             }
44         }
45         int ans=0;
46         for(int i=1;i<=n;i++) if(st[i]==i) ans++;
47         if(ans>1)//不连通
48             cout<<0<<endl;
49         else{
50             int f=0;
51             for(int i=1;i<=n;i++) if(in[i]%2) f=1;
52             if(f) cout<<0<<endl;
53             else cout<<1<<endl;
54         } 
55     }
56     return 0;
57 }

View Code

并查集~

总结：欧拉回路存在条件

　　　　1，图连通

　　　　2，图中各点的度全部为偶数

关于欧拉回路与欧拉路径的判断->>>>>自家博客