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 } 

 

一周排行
  • 如果不修改默认后台地址总会感觉安全性靠不住.出于这个考虑,我今天也一直在想办法修改默认的后台地址 zblog是一款非常强大的博客网站系统,以前一直都是asp版本,最近出了php版本,对于喜欢用php程序来建站的站长来 ...
  • 你是否曾经想过从jsp页面(或者servlet)中发送动态产生的图像?这篇技巧告诉你如何做.要运行这里的代码,你需要一个Tomcat或者其他支持JSP 1.1的web服务器. 当一个web页面带有image/jpeg ...
  • 操作数的都是char *型,操作时不考虑末尾的'\0'. strlen:字符串求长 返回字符串或指针的实际大小,与sizeof()的区别参见:www.cnblogs.com/carekee/articles/1630 ...
  • JavaScript的运行环境和代码位置 编写JavaScript脚本不需要任何特殊的软件,一个文本编辑器和一个Web浏览器就足够了,JavaScript代码就是运行在Web浏览器中. 用JavaScript编写的代 ...
  • (1)查看库信息 select * from v$version (2)查看字符集 select * from sys.props$ wherename='NLS_CHARACTERSET'; 1. 进程查看 l 数 ...
  • 在之前的博客中,总结了Excel模板生成和Excel数据录入,然后剩最后一个模块,数据库中数据读取,在之前的基础上我们来看这一模块,应该已经非常容易了,接下来简单的介绍一下: 这里我们仍然以jsp+servlet为例 ...
  • 查看系统运行状态的命令top [[email protected]~]#top [选项] 选项: -d 秒数 指定top命令每个几秒更新.默认为3秒 在top命令的交互模式当中可以执行的命令 ?或h 查看帮助 P 以CPU ...
  • FT232RL是个是神奇的片子,说万能可能有些夸张,但是...总之就是FTDIChip这个神奇的公司基于类似的技术,做了很多好用的产品,包括转IIC啦,转SPI啦,密码狗啦之类的.是个很有用的工具就对了. 言归正传. ...
  • 苹果公司今天正式发布了iOS 7.1系统更新,这是该公司对其iOS操作系统进行的最新一次重大更新 苹果公司今天正式发布了iOS 7.1系统更新,这是该公司对其iOS操作系统进行的最新一次重大更新. iOS 7.1对备 ...
  • #include <iostream> using namespace std; class Stu { public: Stu (int n,string nam); void display(); p ...