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 } 

 

一周排行
  • 近日,接到网友发现猫扑论坛被黑客挂马,而且已经超过两天时间尚未被猫扑论坛相关人员发现. 事件过程: 12月22日,在安全厂商举办的网络公益杀毒活动中,网友猫扑论坛被黑客挂马.超级巡警实验室(sucop.com)的反病 ...
  • DoNews游戏4月29日消息(见习记者 赵玥)西山居CEO邹涛发布公司2014年两大战略:保持端游<剑网3>100%增长幅度和推出款精品手游,并表示将重心转向手游的研发和发行.邹涛认为,保持端游& ...
  • 问: 我有两年作为网络管理员的经验,但我很想通过我的努力成为信息安全的专业人士.你认为我应该采取哪些步骤?我应该学习什么,或者应该获得什么认证吗? 答: 首先,我应该祝贺你,因为你选择了一个令人兴奋的领域.我所知道的 ...
  • 作者: smile XSS(Cross-site scripting)攻击是最常见的Web攻击之一,和其它Web攻击类似的是,XSS也是利用Web页面编码的不严谨,和SQL注入漏洞所不同的是,XSS漏洞更加难以发现避 ...
  • 3.Java类型和本地类型对应 在如下情况下,需要在本地方法中应用java对象的引用,就会用到类型之间的转换: 1)java方法里面将参数传入本地方法: 2)在本地方法里面创建java对象: 3)在本地方法里面ret ...
  • /// /// 行列式计算,本程序属于MyMathLib的一部分,欢迎使用,参考,提意见. /// 有时间用函数语言改写,做自己得MathLib,里面的算法经过验证,但没经过 /// 严格测试,如需参考,请慎重. / ...
  • #include <stdio.h> #include <string.h> #include <stdlib.h> #include <queue> using na ...
  • 网上找一篇文章,也不知道是谁写的,所以也就这样用了,也就没写出处了. 顺利做好IP反向解析(PTR记录) 在垃圾邮件泛滥的今天,垃圾邮件给我们的生活.工作.学习带来了极大的危害.由于SMTP服务器之间缺乏有效的发送认 ...
  • 循环语句 l  在程序中C++有5种方法执行重复操作: 1.         for:  循环前检查条件 2.         while: 循环前检查条件 3.         do/while循环后检查条件 4. ...
  • http://blog.csdn.net/pipisorry/article/details/39231949 Python基本输入输出教程 一.内置输入函数 先在交互式解释器中查看input函数的具体情况. [py ...