Uvaoj10054

Uvaoj10054

 1 /*
 2     题意:打印欧拉回路!
 3     思路:开始时不明白,dfs为什么是后序遍历? 
 4     因为欧拉回路本身是一条回路,那么我们在dfs时,可能存在提前找到回路,这条回路可能不是欧拉回路,
 5     因为没有遍历完成所有的边!如果写成前序遍历的话,存储起来的路径就不是一条完整的路径了!它有可能
 6     是多条回路组成的!答案就是错误 的!如果是后序遍历的话,当dfs是遇到了回路,那么就退出当前栈的搜索!
 7     去寻找其他的路径!最终得到的只有一条回路路径!-->欧拉回路~! 
 8 */ 
 9 #include<iostream>
10 #include<cstring>
11 #define M 55
12 #define Max 0x3f3f3f3f
13 using namespace std;
14 
15 int cnt[M][M];
16 int deg[M];
17 int map[M][M];
18 int x;
19 
20 struct Point{
21    int x, y;
22    Point(){}
23    
24    Point(int x, int y){
25       this->x=x;
26       this->y=y; 
27    }
28 }; 
29 
30 Point p[1005];
31 int top;
32 
33 void dfs(int u){
34    if(!deg[u]) return;
35    for(int i=1; i<=50; ++i)
36      if(map[u][i] && cnt[u][i]){
37          --cnt[u][i];
38          --cnt[i][u];
39          --deg[u];
40          --deg[i];
41          dfs(i);
42          p[++top]=Point(u, i); 
43      } 
44 }
45 
46 int main(){
47    int t, n, k=0;
48    cin>>t;
49    while(t--){
50       cin>>n;
51       x=Max;
52       memset(cnt, 0, sizeof(cnt));
53       memset(map, 0, sizeof(map));
54       memset(deg, 0, sizeof(deg));
55       for(int i=1; i<=n; ++i){
56           int u, v;
57           cin>>u>>v;
58           deg[u]++;
59           deg[v]++;
60           map[u][v]=1;
61           map[v][u]=1;
62           cnt[u][v]++;
63           cnt[v][u]++;
64           if(x>u) x=u;
65           if(x>v) x=v;
66       }
67       int ok=0;
68       for(int i=1; i<=50; ++i)
69          if(deg[i]%2!=0){
70             ok=1;
71             break;
72          }
73       cout<<"Case #"<<++k<<endl;
74       if(ok){
75          cout<<"some beads may be lost"<<endl;
76          if(t) cout<<endl;
77          continue;
78       }
79       top=0;
80       dfs(x);
81       if(top==n){
82          for(top; top>=1; --top)
83             cout<<p[top].x<<" "<<p[top].y<<endl;
84       }
85       else cout<<"some beads may be lost"<<endl;      
86       if(t) cout<<endl; 
87    }
88    return 0;
89 } 

 

一周排行
  • Angular服务 在angular中,服务(service)是以提供特定的功能的形式而存在的. angular本身提供了很多内置服务,比如: $q: 提供了对promise的支持. $http: 提供了对ajax的 ...
  • VPN对于企业信息化的建设,已经是不可缺少的一环了.随着进销存.财务.ERP.CRM等软件的的普及,很多中小企业为了达到进一步针对远程存取的目的,开始进行VPN环境的建置.有了VPN,中小企业的分支机构及移动用户,可 ...
  • 之前这篇文章放在草稿箱中很久了,最近我要清理博客的数据库,就发表出来吧.   statpresscn是流行的wordpress站点统计插件的中文版,虽然已经很久未更新,而且wp官网统计也仅仅不到10万次下载:但因为这 ...
  • 代码在http://www.cnblogs.com/ouqifeng/内 总结:通过这次实验,我觉得我们的收获还是挺大的,首先这个实验要求我们能够提高效率,因为结对的作用就是为了提高工作的效率,这方面我们还是做到了, ...
  • 巨人网络董事长史玉柱在ChinaJoy期间的一场聚会上表示,网页游戏将面临爆炸式增长机会,而巨人已经开始拥抱这种变化."客户端火拼了10年,研发和推广的门槛越来越高.相比之下,页游非常适合有梦想的年轻人创业 ...
  • 原文 作为程序员,我们离不开使用各种图形来描述软件.毕竟,图形描述方法比起直接看代码更加形象,更符合我们的思维方式.大多数的绘图软件,比如viso或者dia,都可以满足一般软件开发中对于绘图的需求了.无论是UML还是 ...
  • 百度百科 百科一下,你就知道 百度百科很好,但是还可以再方便一点,像金山词霸一样,可以屏幕取词..就不用那么麻烦复制不懂的词 粘贴到搜索框进行搜索. 但是屏幕取词会把所有的词都"百科"出来,很麻烦 ...
  • 一些 ASP.NET + Oracle 11g 系统边写边学的随笔,包括引用 Oracle 官方的 Data Provider.更改 Oracle 存储的日期格式.(八) 引用 Oracle 官方的 Data Pro ...
  • From http://www.zend.com/en/products/studio 注:唯一的缺点是收费.
  •      上次说了一下在网页里面显示列表数据的情况,这个应用范围太小了,添加.修改怎么办呢?网站的后台管理.OA.CRM等怎么办?还是这样处理显然是不行的.   我们还是看一个小例子,这回是数据库设计的.   Dic ...