1126. Eulerian Path (25)

/*离散数学中对于欧拉图的定义:通过图（有向或无向）中所有边一次且仅一次行遍所有顶点的通路 称作欧拉通路，通过图中所有边一次且仅一次行遍所有顶点的回路称作欧拉回路，具有欧拉回路的图为欧拉图，具有欧拉通路的图为半欧拉图。*//*    定理1:无向图G是欧拉图当且仅当G时连通图且没有奇度顶点    定理2:无向图G是半欧拉图当且仅当G是连通的且恰有两个奇度顶点*/#include <bits/stdc++.h>using namespace std;const int maxn = 510;vector<int>  Adj[maxn];//模拟了邻接表bool vis[maxn] = { false };int cnt = 0;//记录连通点的个数void DFS(int ans){    vis[ans] = true;    cnt++;    for ( int i = 0; i < Adj[ans].size(); i++ ) {        int v = Adj[ans][i];        if ( !vis[v] )        {            DFS(v);        }    }}int main(){    int n,m;    int evens = 0;    cin >> n >> m;    int u,v;    for ( int i = 0; i < m; i++ )    {        cin >> u >> v;        Adj[u].push_back(v);        Adj[v].push_back(u);    }    for ( int i = 1; i <= n; i++ )    {        if ( i == 1 ) cout << Adj[i].size();        else cout << " " << Adj[i].size();        if ( Adj[i].size()%2 == 0 ) evens++;    }    cout << endl;    DFS(1);    if ( cnt == n && evens == n)        cout << "Eulerian" << endl;    else if ( cnt == n && evens == n-2 )        cout << "Semi-Eulerian" << endl;    else        cout << "Non-Eulerian" << endl;    return 0;}