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 } 

 

一周排行
  • Core Data是一个功能强大的层,位于SQLite数据库之上,它避免了SQL的复杂性,能让我们以更自然的方式与数据库进行交互.Core Data将数据库行转换为OC对象(托管对象)来实现,这样无需任何SQL知识就 ...
  • select连接查询 简要: 一.union联合查询 二.左右内连接 一.union联合查询 作用: 把2次或多次查询结果合并起来 详细: (表1查询结果) union (表2查询结果) 执行: 先算表1查询结果,再 ...
  • 1,文件系统,从/开始的树状结构 2,绝对路径:/打头,相对路径:从当前目录下开始的 3,usename,passwd,uid,gid,home,shell(都是管理员指定的,这些信息都在passwd文件中(只读)) ...
  • 在测试中发现iPad上的Safari总会把长串数字识别为电话号码,文字变成蓝色,点击还会弹出菜单添加到通讯录. 别的地方倒也罢了,如果在用户名中出现数字(手机注册新浪微博的话用户名就是“手机用户xxxxxxxx”), ...
  • public class StringTools {    public StringTools() {    }    //取得拼音码    public String getPinYM(String a) {   ...
  • 必须承认,Web 开发实在不是多么愉快的工作,虽然,近年来,一些也算是有趣的工具在源源不断地推出,诸如 Rubby on Rails, Ajango 一类的框架,诸如 jQuery, Dojo 一类的 JavaScr ...
  • 5月15日消息,亲贝网CEO刘阳今日爆料,国内手机摄像软件商Camera 360将于近期推出拍照手机.
  • 环境:JDK 1.6.31 问题:Java集合框架总结   以往Java的集合框架都是自学的,现在课堂上也讲了,学习起来轻松了许多,更好的是,发现了两张很好的图,所以贴上来和大家分享.   1.集合类比较表:     ...
  • 用法一:常量 在JDK1.5 之前,我们定义常量都是: publicstaticfianl.... .现在好了,有了枚举,可以把相关的常量分组到一个枚举类型里,而且枚举提供了比常量更多的方法.   Java代码  p ...
  • 注:工业4.0的大幕徐徐开启,全球工业制造都正向智能制造转型,仍然徘徊在价值链底端的中国企业如何快速转型.把握产业链上稍纵即逝的新机遇.如何避免出局?中国企业亟待思考如何把握产业物联网带来的机遇,拓展"产品 ...