哥尼斯堡是位于普累格河上的一座城市，它包含两个岛屿及连接它们的七座桥，如下图所示。
可否走过这样的七座桥，而且每桥只走过一次？瑞士数学家欧拉(Leonhard Euler，1707—1783)最终解决了这个问题，并由此创立了拓扑学。
这个问题如今可以描述为判断欧拉回路是否存在的问题。欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个无向图，问是否存在欧拉回路？
输入格式:
输入第一行给出两个正整数，分别是节点数N (1≤N≤1000)和边数M；随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个节点的编号（节点从1到N编号）。
输出格式:
若欧拉回路存在则输出1，否则输出0。
输入样例1:
6 10
1 2
2 3
3 1
4 5
5 6
6 4
1 4
1 6
3 4
3 6输出样例1:
1输入样例2:
5 8
1 2
1 3
2 3
2 4
2 5
5 3
5 4
3 4输出样例2:
0思路：
1. 无向图是欧拉图（存在欧拉回路）当且仅当该图是连通的且没有奇度顶点；无向图是半欧拉图（存在欧拉通路）当且仅当该图是连通的且恰有两个奇度顶点；
有向图是欧拉图（存在欧拉回路）当且仅当该图是强连通的且每个顶点入度等于出度；有向图是半欧拉图（存在欧拉通路）当且仅当该图是单向连通的且恰有两个奇度顶点；
2. 本题中首先需要判断该图是否连通图，若是连通图则再判断是否有无奇度顶点；
3. 使用并查集来判断该图是否为连通图，设置一个数组ab，每个元素初始化为对应下标（每个元素的根结点为自己），每输入一条边，便在数组ab中寻找边的顶点a和b（a<b）的根结点fa和fb，若fa和fb不相等（没有在一个连通分支里），则把fb指向fa（fa作fb的根结点）；
4. 使用一个数组v，每个元素初始化0，每输入一条边，便在数组v中增加对应顶点a和b和度数；
5. 找出每个顶点在并查集数组ab中的根结点，并判断是否都相等，相等则为连通图；
6. 根据数组v判断每个顶点的度数是否为偶数；全为偶数则是欧拉图（前提是5成立）；
//7-32 哥尼斯堡的“七桥问题”
#include <iostream>
using namespace std;
#include <algorithm>
#include <vector>
#include <set>
#define N 1005
int ab[N],n; //ab为并查集数组
int find(int x) //寻找x的根结点
{
if(x==ab[x]) return x;
return ab[x]=find(ab[x]);
}
bool liantong() //判断是否为连通图
{
set <int> se;
for(int i=1;i<=n&&se.size()<=1;i++)
se.insert(find(i));
if(se.size()==1)
return true;
return false;
}
bool degreeOK(vector<int> v) //判断连通无向图是否为欧拉图
{
for(int i=1;i<=n;i++)
if(v[i]%2!=0)
return false;
return true;
}
int main()
{
int m,i,a,b;
cin>>n>>m;
vector<int> v(n+1,0); //统计度数
for(i=1;i<=n;i++) //初始化并查集数组
ab[i]=i;
for(i=0;i<m;i++)
{
cin>>a>>b;
if(a>b)
swap(a,b); //避免互相指向（循环指向）产生多个根节点，对所有节点都是大的指向小的
v[a]++;v[b]++;
int fa=ab[a]; //找出a的跟节点fa
int fb=ab[b]; //找出b的跟节点fb
if(fa!=fb)
ab[fb]=fa; //合并，fb指向fa,大的指向小的
}
if(liantong()&°reeOK(v)) //连通且无奇度顶点
cout<<1<<endl;
else
cout<<0<<endl;
return 0;
}
