题目描述

在图论中，欧拉路径是图中的一条路径，该路径满足恰好访问每个边一次。

而欧拉回路是一条在同一顶点处开始和结束的欧拉路径。

它们最早由欧拉于 1736 年解决著名的哥尼斯堡七桥问题时提出。

事实证明，如果一个连通图的所有顶点的度数都为偶数，那么这个连通图具有欧拉回路，且这个图被称为欧拉图。

如果一个连通图中有两个顶点的度数为奇数，其他顶点的度数为偶数，那么所有欧拉路径都从其中一个度数为奇数的顶点开始，并在另一个度数为奇数的顶点结束。

具有欧拉路径但不具有欧拉回路的图被称为半欧拉图。

现在，给定一个无向图，请你判断它是欧拉图、半欧拉图还是非欧拉图。

输入格式
第一行包含两个整数 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

输出样例1：

2 4 4 4 4 4 2
Eulerian

输入样例2：

6 10
1 2
1 3
2 3
2 4
3 4
5 2
6 3
4 5
6 4
5 6

输出样例2：

2 4 4 4 3 3
Semi-Eulerian

输入样例3：

5 8
1 2
2 5
5 4
4 1
1 3
3 2
3 4
5 3

输出样例3：

3 3 4 3 3
Non-Eulerian

dfs求连通性

C++ 代码

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;
const int N = 505;
int n, m;
int g[N][N];
bool st[N];
int d[N];
int t, cnt;

void dfs(int u)
{
    st[u] = true;
    cnt ++;

    for(int i = 1; i <= n; i ++ )
        if(g[u][i] && !st[i]) dfs(i);
}

int main()
{
    scanf("%d%d", &n, &m);
    while(m --)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        g[a][b] = g[b][a] = 1;
        d[a] ++, d[b] ++;
    }

    for(int i = 1; i <= n; i ++ )
    {
        printf("%d%c", d[i], i == n ? '\n' : ' ');
        if(d[i] % 2 != 0) t ++;
    }

    dfs(1);

    if(cnt == n)
    {
        if(t == 0) puts("Eulerian");
        else if(t == 2) puts("Semi-Eulerian");
        else puts("Non-Eulerian");
    }
    else puts("Non-Eulerian");
    return 0;
}

blablabla

并查集集求联通性

blablabla

时间复杂度

参考文献

C++ 代码

blablabla