首页 > > 程序设计 > C/C++ >

一笔画问题

2018-06-17 22:51:49来源：未知阅读 ()

l样例输入:第一行n，m，有n个点，m条边，以下m行描述每条边连接的两点。

l 5 5

l 1 2

l 2 3

l 3 4

l 4 5

l 5 1

l样例输出:欧拉路或欧拉回路

l 1 5 4 3 2 1

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int map[1001][1001];
 5 int tj[10001];
 6 int vis[1001];
 7 int n,m;
 8 int ans[1001];
 9 int now=1;
10 int flag=1;
11 void dfs(int i) {
12     //cout<<p<<" ";
13     for(int j=1; j<=n; j++) 
14     {
15         if(map[i][j]==1) 
16         {
17             map[j][i]=map[i][j]=0;
18             dfs(j);
19         }
20     }
21     ans[now]=i;
22     now++;
23 }
24 int main() 
25 {
26 
27     scanf("%d%d",&n,&m);
28     for(int i=1; i<=m; i++) 
29     {
30         int x,y;
31         scanf("%d%d",&x,&y);
32         map[y][x]=map[x][y]=1;
33         tj[x]++;
34         tj[y]++;
35     }
36     flag=1;
37     for(int i=1; i<=n; i++) 
38         if(tj[i]%2==1) 
39         {
40             flag=i;
41         }
42     dfs(flag);
43     for(int i=1; i<=now-1; i++)
44     cout<<ans[i]<<" ";
45     return 0;
46 }