欧拉图入门
引言
18世纪初普鲁士的哥尼斯堡，有一条河穿过，河上有两个小岛，有七座桥把两个岛与河岸联系起来（如概述图）。有个人提出一个问题：一个步行者怎样才能不重复、不遗漏地一次走完七座桥，最后回到出发点。后来大数学家欧拉把它转化成一个几何问题——一笔画问题。他不仅解决了此问题，且给出了连通图可以一笔画的充要条件是：奇点的数目不是0个就是2个（连到一点的数目如果是奇数条，就称为奇点；如果是偶数条，就称为偶点。要想一笔画成，必须中间点均是偶点，也就是有来路必有另一条去路，奇点只可能在两端。因此任何图能一笔画成，奇点要么没有，要么在两端）。
1736年29岁的欧拉向圣彼得堡科学院递交了《哥尼斯堡的七座桥》的论文，在解答问题的同时，开创了数学的一个新的分支——图论与几 何拓扑，也由此展开了数学史上的新历程。 七桥问题提出后，很多人对此很感兴趣，纷纷进行试验，但在相当长的时间里，始终未能解决。欧拉通过对七桥问题的研究，不仅圆满地回答了哥尼斯堡居民提出的问题，而且得到并证明了更为广泛的有关一笔画的三条结论，人们通常称之为“欧拉定理”。
欧拉图相关定义
它们最早由欧拉于 1736 年解决著名的哥尼斯堡七桥问题时提出。
欧拉路径
在图论中，欧拉路径 是图中的一条路径，该路径满足恰好访问每个边一次。
欧拉回路
欧拉回路 是一条在同一顶点处开始和结束的欧拉路径。
欧拉图
事实证明，如果一个连通图的所有顶点的度数都为偶数，那么这个连通图具有欧拉回路，且这个图被称为欧拉图。
具有欧拉路径但不具有欧拉回路的图被称为 半欧拉图。
欧拉路径判定：
有向图欧拉路径：图中恰好存在 1 个点出度比入度多 1（这个点即为 起点 S），1 个点入度比出度多 1（这个点即为 终点 T），其余节点出度=入度。
有向图欧拉回路：所有点的入度=出度（起点 S 和终点 T 可以为任意点）。
无向图欧拉路径：图中恰好存在 2 个点的度数是奇数，其余节点的度数为偶数，这两个度数为奇数的点即为欧拉路径的 起点 S 和 终点 T。
无向图欧拉回路：所有点的度数都是偶数（起点 S 和终点 T 可以为任意点）。
注：存在欧拉回路（即满足存在欧拉回路的条件），也一定存在欧拉路径。
判定
现在，给定一个无向图，请你判断它是欧拉图、半欧拉图还是非欧拉图。
输入格式
第一行包含两个整数 N 和 M，表示无向图的点和边的数量。接下来 M 行，每行包含两个整数 a,b，表示点 a 和 b 之间存在一条边。
所有点的编号从 1∼N。数据保证图是联通的。
输出格式
首先，在第一行按顺序输出点 1∼N 中每个点的度数。
第二行输出对该图的判断，Eulerian（欧拉图），Semi-Eulerian（半欧拉图），Non-Eulerian（非欧拉图）。
1< =N < =500; 1< = M< = N*(N-1)/2
输入/输出例子1
输入：
7 12
5 7
1 2
1 3
2 3
2 4
3 4
5 2
7 6
6 3
4 5
6 4
5 6
输出：
2 4 4 4 4 4 2
#include <bits/stdc++.h>
using namespace std;
int N,M;
int a[505][505];
int flag;
int ans;
int main()
{
cin>>N>>M;
for (int i = 1; i <= M; i++)
{
int x,y;
cin>>x>>y;
a[x][y]++;
a[y][x]++;
}
for (int i = 1; i <= N; i++)
{
int td = 0;
for (int j = 1; j <= N; j++)
{
if (a[i][j])
{
td += a[i][j];
}
}
cout<<td<<" ";
if (td % 2 == 1) flag++;
}
cout<<endl;
if (flag == 0)
cout<<"Eulerian"<<endl;
else if (flag == 2)
cout<<"Semi-Eulerian"<<endl;
else
cout<<"Non-Eulerian"<<endl;
return 0;
}