游客 注册 | 登录
中文 | En

2391 - 欧拉路

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

      有一个图，图中要么有两个奇点要么0奇点，如果是欧拉回路请从第一个点为起点开始遍历，如果有两个奇点，则以字典序大的为起点开始遍历，在遍历的过程中，字典序小的先遍历。

题目输入

第一行两个整数，n和e，表示有n个节点，e条边

题目输出

只有一行，为欧拉路或欧拉回路。

输入/输出样例

输入格式

5 5
1 2
2 3
3 4
4 5
5 1

输出格式

1 5 4 3 2 1

C语言解答

#include<stdio.h>
#include<string.h>

int a[105][105]; 
int du[105];
int n,e,start,df;
void init();
void dfs(int);

int main()
{
	init();
	dfs(start);
	return 0;
}

void dfs(int x)
{
		for(int i=1;i<=n;i++)
	{
		if(a[x][i]==1)
		{
			a[x][i]=a[i][x]=0;
			dfs(i); 
		}
	}
	printf("%d ",x);
}

void init()
{
	memset(a,0,sizeof(a));
	memset(du,0,sizeof(du));
	scanf("%d%d",&n,&e);
	int x,y;
	for(int i=1;i<=e;i++)
	{
		scanf("%d%d",&x,&y);
		a[x][y]=a[y][x]=1;
		du[x]++; 
		du[y]++;
	}
	start=1;
	for(int i=1;i<=n;i++)
	  if(du[i]%2==1)  start=i;
	 }

C++解答

#include<iostream>
#include<cstring>
#include<cstdio> 
using namespace std;
int a[100][100];//邻接矩阵存储节点关系 
int du[100];//记录每个节点的度数 
int n,e,start;
void init();
void dfs(int);
int main()
{
	//freopen("euler1.in","r",stdin);
	//freopen("euler1.out","w",stdout);
	init();
	//cout<<"start="<<start<<endl;
	dfs(start);
	return 0;
}
void init()
{
	memset(a,0,sizeof(a));
	memset(du,0,sizeof(du));
	cin>>n>>e;
	int x,y;
	for(int i=1;i<=e;i++)
	{
		cin>>x>>y;
		a[x][y]=a[y][x]=1;//无向图 
		du[x]++;//x节点度数++ 
		du[y]++;//y节点度数++		
	}
	start=1;//遍历所有节点找到第一个奇点，没奇点则为1 
	for(int i=1;i<=n;i++)
	  if(du[i]%2==1)
	  {
	  	start=i;
	  	//break;
	  }
}
void dfs(int x)
{	 	
	for(int i=1;i<=n;i++)
	{
		if(a[x][i]==1)//找到下一个邻接点 
		{
			a[x][i]=a[i][x]=0;//两条边均设为0，不会重复访问 
			dfs(i);//以邻接点开始遍历 
		}
	}
	cout<<x<<' ';//输出当前节点	
}
请先登陆