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