/*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;
}
模板-邻接表DFS遍历
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
