一笔画问题

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

新老客户大回馈,云服务器低至5折

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 }

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:哈密尔顿环问题

下一篇:1722 最优乘车 1997年NOI全国竞赛