题意:若图是连通图,且所有结点的度均为偶数,则称为Eulerian;若有且仅有两个结点的度为奇数,则称为semi-Eulerian。现给出一个图,要我们判断其是否为Eulerian,semi-Eulerian还是not-Eulerian。
思路:在数据输入的时候计算各个节点的度;在输出各个节点的度的同时记录度为奇数的结点个数;最后判断判断图是否连通。这种题不考察什么算法,关键要我们理解题意,往往都是很简单的!
代码:
#include <cstdio> #include <cstring> #include <vector> using namespace std; ; vector<int> Adj[maxn]; }; int vis[maxn]; int n,m,u,v; void dfs(int v) { vis[v]=true; for(auto u:Adj[v]) if(!vis[u]) dfs(u); } bool connected() { memset(vis,false,sizeof(vis)); ;//连通块的个数 ;v<=n;v++){ if(!vis[v]){ dfs(v); cnt++; } } ? false : true); } int main() { //freopen("pat.txt","r",stdin); scanf("%d%d",&n,&m); ;i<m;i++){ scanf("%d%d",&u,&v); Adj[u].push_back(v); Adj[v].push_back(u); degree[u]++; degree[v]++; } ; ;v<=n;v++){ !=) oddCnt++; printf("%d",degree[v]); if(v==n) printf("\n"); else printf(" "); } bool flag=connected(); ) printf("Eulerian\n"); ) printf("Semi-Eulerian\n"); else printf("Non-Eulerian\n"); ; }