1126 Eulerian Path（25 分）

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<set>

using namespace std;

int M, N, a, b;
vector<vector<int>>vm;
vector<int>v;
vector<bool>visit;
set<int>s;

void DFS(int num)
{
    if (visit[num] == true)     
        { return; }
    visit[num] = true;
    for (int j = 0; j < vm[num].size(); j++)
    {
        if (visit[vm[num][j]] == false)
        {
            s.insert(vm[num][j]);
            DFS(vm[num][j]);
        }
    }
}

int main()
{
    bool flag = false;
    cin >> M>>N;
    vm.resize(M);
    v.resize(M);
    visit.resize(M);

    for (int i = 0; i < N; i++)
    {
        cin >> a >> b;
        a--;
        b--;
        v[a]++;
        v[b]++;

        vm[a].push_back(b);
        vm[b].push_back(a);
    }


    DFS(0);
    s.insert(0);
    
    int cnt = 0;
    cout << v[0];
    if (v[0] % 2 == 0) cnt++;

    for (int i = 1; i<v.size(); i++)
    {
        cout << " " << v[i];
        if (v[i]== 0) flag=true;
        if (v[i] % 2 == 0) cnt++;
    }
    cout << endl;

    if (s.size() != M)
    {
        cout << "Non-Eulerian" << endl;
        return 0;
    }
    if ((cnt==M)&&flag==false)
    {
        cout << "Eulerian" << endl;
        
    }
    else if ((cnt == M-2)&&flag ==false)
    {
        cout << "Semi-Eulerian" << endl;
    }
    else
    {
        cout << "Non-Eulerian" << endl;
    }
    system("pause");
    return 0;
}