模板-邻接表DFS遍历

/*Eulerian:所有节点度数都不是奇数的连通无向图
semi-Eulerian:有2个节点度数是奇数的连通无向图
non-Eulerian:不符合上述两条的连通无向图，以及非连通无向图

注意题目给出的图只保证是无向图，不保证是否连通*/
 
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
const int MAXV=201,INF=1000000;
int N,M,cnt=0;
vector<int> Adj[MAXV];
bool vest[MAXV]= {false};
void DFS(int v)
{
    vest[v]=true;
    for(int i=0; i<Adj[v].size(); i++)
    {
        if(vest[Adj[v][i]]==false)//注意邻接表DFS遍历与邻接矩阵FDS遍历的区别,详见算法笔记P353页
            DFS(Adj[v][i]);
    }
}

//统计某图中，度为奇数的节点个数
int oddDegree()
{
    int sum=0;
    for(int i=0; i<N; i++)
    {
        if(Adj[i].size()%2!=0)
            sum++;
    }
    return sum;
}


int main()
{

    cin>>N>>M;
    int u,v;
    for(int i=0; i<M; i++)
    {
        cin>>u>>v;
        Adj[u-1].push_back(v-1);
        Adj[v-1].push_back(u-1);
    }

    for(int i=0; i<N; i++)
    {
        if(vest[i]==false)
        {
            cnt++;
            DFS(i);
        }
    }

    cout<<Adj[0].size();

    for(int i=1;i<N;i++)
    {
        cout<<" "<<Adj[i].size();
    }
    cout<<endl;

    if(cnt>1)
    {
        cout<<"Non-Eulerian"<<endl;
        return 0;
    }

    if(oddDegree()==0)
    {
        cout<<"Eulerian"<<endl;
        return 0;
    }
    if(oddDegree()==2)
    {
        cout<<"Semi-Eulerian"<<endl;
        return 0;
    }
    cout<<"Non-Eulerian"<<endl;
    return 0;
}