学步园

欧拉图（欧拉通路，欧拉回路）

给你一副无向图。 寻找一条包含所有边的路径，其中每一条边只经过一次。这被叫做欧拉通路。
若这条路径的起点与终点为同一点，则为欧拉回路。

判定定理：
定理1：一个图有欧拉回路当且仅当它是连通的（即不包括0度的结点）且每个结点都有偶数度。
定理2：一个图有欧拉通路当且仅当它是连通的且除两个结点为基数度，其他结点都有偶数度。
       其中的两个基数度结点分别为起点和终点。

int map[MAXN][MAXN]; //map[i,j]表示i,j之间的边的条数
int deg[MAXN];       //记录结点的度

/*  递归实现 */
void DFS(int s)
{
    int i;
    for (i=1; i<=500; i++)
        if (map[s][i])
        {
            map[s][i]--;
            map[i][s]--;
            DFS(i);
        }
    ans[num++] = s;
}
int main()
{
    for (k=0; k<n; k++)
    {
        scanf("%d %d", &i, &j);
        map[i][j]++;
        map[j][i]++;
        deg[i]++;
        deg[j]++;
    }
    DFS(start);
	//最后把ans[]逆序输出即为路径顺序。
}