前几天去刷了PAT,趁热把答案记录下来供大家参考
这题完全是英语阅读题,题目读懂就能写
我考试的时候花了起码10分钟去读题,英语实在太渣
第3个测试点是个坑点,考的时候提交了11次才出来
第3个测试点:关键字:connected graph,要先判断图是否是一个连通图
#include<stdio.h> #include<algorithm> using namespace std; const int INF=1000000000; int n, m; int G[510][510]; int degree[510]={0};//记录每个顶点的边数 bool vis[510]={false}; int num=0; void DFS(int v){//判断图是否连通 num++; vis[v]=true; for(int i=1;i<=n;i++){ if(!vis[i]&&G[v][i]==1){ DFS(i); } } } int main(){ int i, id1, id2; int even=0, odd=0; fill(G[0],G[0]+510*510,INF);//初始化图的每两个顶点之间都不连通 scanf("%d%d",&n,&m); for(i=0;i<m;i++){ scanf("%d%d",&id1,&id2); degree[id1]++; degree[id2]++; G[id1][id2]=G[id2][id1]=1;//1表示两个顶点间存在边 } for(i=1;i<=n;i++){ if(degree[i]%2==0)even++; else odd++; } DFS(1); for(i=1;i<=n;i++){ printf("%d",degree[i]); if(i<n)printf(" "); else printf("\n"); } if(num==n&&even==n)printf("Eulerian"); else if(num==n&&odd==2)printf("Semi-Eulerian"); else printf("Non-Eulerian"); return 0; }