Eulerian Path(欧拉路径,我英语好菜~)

题目大意:如果一个连通图的所有顶点的度都是偶数,那么它是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 }

Eulerian Path(欧拉路径,我英语好菜~)

 

上一篇:Codeforces 1354E(Graph Coloring,二分图+dp)


下一篇:NORDIC 52832串口校验功能