PAT 1126 C++版

PAT 1126 C++版

1.题意

在图论中，欧拉路径的定义是：在一个图中，可以沿着某条路径能够访问所有的边并且仅访问一次。相似的，欧拉回路值的就是起点和订点相同的欧拉路径。

It has been proven that connected graphs with all vertices of even degree have an Eulerian circuit, and such graphs are called Eulerian.

已经被证明： 在一个连通图中，如果所有的订点都具有偶数度，那么该连通图就有一个Eulerian circuit，这样的图就被称之为 Eulerian。

If there are exactly two vertices of odd degree, all Eulerian paths start at one of them and end at the other.

如果仅仅有两个顶点有奇数度，所有的Eulerian paths 以他们其中的一个开始并且以另一个订点结束。

A graph that has an Eulerian path but not an Eulerian circuit is called semi-Eulerian.

有一个Eulerian path但是没有一个Eulerian circuit的图被称为semi-Eulerian。其它的则被称之为non-Eulerian。

2.分析

• 理解了题目意思就很好做这道题了，在输入数据的时候就针对每个顶点计算其度数，保存在一个数组中。
• 遍历这个数组，然后得到一个度数为奇数的顶点数oddNum。如果顶点数oddNum为0，则表示是一个欧拉回路；如果oddNum=2 ，则说明是一个欧拉路径；如果oddNum为一个其他数，则表明是一个Non-Eulerian。
• 必须遍历一下是否是连通图。如果不是连通图，则上述的条件都不成立。【5分测试点】，当然测试图是否联通很简单，只需要判断一下数目即可。

3.代码

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

struct node{
	int child[10000];
	int curIndex = 0;//表示当前孩子数 
	int isVisit = 0;//初始化未访问 
};

node n[501]; 
int count = 0;//联通的节点数 

//判断图是否联通 
void isConnect(int root){
	if(n[root].isVisit == 1) return; 
	else {
		n[root].isVisit = 1;//设置为1
		count++;
	}
	for(int i = 0;i< n[root].curIndex;i++ ){//取所有的孩子 
		isConnect(n[root].child[i]);	 
	}
} 

int main(){
	int ver,edge;//the number of vertex ; the number of edge
	scanf("%d %d",&ver,&edge);
	int i ;
	int res[ver+1];
	int v1,v2;
	memset(res,0,sizeof(res));
		
	for(i = 0;i< edge;i++){
		scanf("%d %d",&v1,&v2);
		n[v1].child[n[v1].curIndex] = v2;
		n[v2].child[n[v2].curIndex] = v1;
		
		n[v1].curIndex++;
		n[v2].curIndex++;
		res[v1]++;
		res[v2]++;
	} 
	
	isConnect(1); 
	//cout << "count = "<< count<<endl;
	if(count != ver){
		cout << "Non-Eulerian" <<endl;		
	}
	else{
		//输出边的度数	
		int oddNum = 0;//度数为奇数的数目	 
		for(i = 1;i< ver+1;i++){
			if(res[i] % 2 != 0) oddNum++;
			cout << res[i];
			if(i != ver) cout << " ";
		}
		cout << endl;
		
		if(oddNum == 0){
			cout<< "Eulerian" << endl;
		}
		else if(oddNum == 2){
			cout<<"Semi-Eulerian"<< endl;
		}else{
			cout << "Non-Eulerian" << endl;
		}	
	}	
} 

4.测试用例

1 0
1

7 12
5 7
1 2
1 3
2 3
2 4
3 4
5 2
7 6
6 3
4 5
6 4
5 6

1 0
1 

2 1
1 2

6 4
1 2
2 3
3 4
5 6

6 4
1 2
3 4
5 6
4 6

5. 执行结果

但是很尴尬，有一个测试点没过╮(╯﹏╰）╭

根据这个5分的测试点，可以看出这应该是一个大点【我猜测是连通图判定】，但是我明明做了这个判断。也不知道为何不行。