题目大意:如果一个连通图的所有顶点的度都是偶数,那么它是Eulerian,如果除了两个顶点的度是奇数其它的是偶数,那么它是semi-Eulerian,否则它是Non-Eulerian。
注意:连通图不一定是Eulerian。
1 #include<iostream> 2 #include<vector> 3 #include<algorithm> 4 using namespace std; 5 6 vector<int> adj[510]; 7 bool visited[510]; 8 int cnt = 0; 9 void DFS(int u) { //判断无向图是否连通 10 visited[u] = true; 11 cnt++; 12 for(int i = 0 ; i < adj[u].size(); ++i) 13 if(visited[adj[u][i]] == false) { 14 DFS(adj[u][i]); 15 } 16 } 17 int main() { 18 int n,m,u,v,flag = -1,even = 0; 19 cin>>n>>m; 20 for(int i = 0; i < m; ++i) { 21 cin>>u>>v; 22 adj[u].push_back(v); 23 adj[v].push_back(u); 24 } 25 for(int i = 1; i <= n; ++i) { 26 if(i > 1) printf(" "); 27 printf("%d",adj[i].size()); 28 if(adj[i].size()%2 == 0) even++; 29 } 30 printf("\n"); 31 DFS(1); 32 if(cnt == n && even == n) printf("Eulerian\n"); 33 else if(cnt == n && even == n-2) printf("Semi-Eulerian\n"); 34 else printf("Non-Eulerian\n"); 35 return 0; 36 }