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 } 

 

一周排行
  • 本文是基于IIS6的处理模型. 当一个客户端页面访问IIS试图获取一些信息的时候,发生了什么事情?一个请求在通过了HTTP管道后又发生了什么?本文主要是描述这两个过程,即IIS处理asp.net请求和asp.net的 ...
  •   'destoon\api\spider.php   if($verify_mode == 4) exit('接口未开启'); if(strpos($_SERVER['PHP_SELF'], '/spider.ph ...
  • 每经记者 赵娜 发自北京昨日(1月7日),京东旗下拍拍网宣布,近期将上线移动店铺管理工具即拍拍微店APP,特点是集成"一键开店"和"一键分销"等功能.拍拍微店相关负责人表示,& ...
  •       先看下效果:                  圆心下的那个那个白圈的位置是光圈的起始位置,光圈所在的位置为终点位置.光圈从起始位置开始,沿着圆的轮廓匀速到终点位置. 在支持css3的情况下,可以利用cs ...
  • 陌生人实时语音社交应用"比邻"今日宣布已完成A轮1500万美元融资,投资方包括启明创投.晨兴创投. 在发布融资消息的同时,比邻同时宣布了几个用户数据:总注册用户目前已突破两千万,日通话总时常突破1 ...
  • 易网科技讯 7月7日消息,智能硬件PaaS平台--AbleCloud(北京智云奇点科技有限公司)宣布已于今年5月完成2500万人民币A轮融资,由信中利资本领投,天使投资方联想之星跟投.据介绍,本轮融资将主要用于组建& ...
  • 问题贴:http://topic.csdn.net/u/20100509/20/045e886c-a38d-4614-a5a4-aa2add05a95b.html?42337 -------------------- ...
  • 1.读取Isolated Storage     每个Metro程序都有三个文件夹:Local,Roaming,Temp.每个文件夹的访问方法都是相同的.     Local用于将数据存储在本地,这是程序特定的文件夹 ...
  • 移动web开发 1.移动web开发(一)——移动web开发必备知识 2.移动web开发(二)——viewport 3.移动web开发(三)——字体使用 4.移动web开发(四)——X-UA-Compatible   ...
  • Call/Apply 因为this指针的指向很容易被转移丢失,因此Javascript提供了两个类似的函数apply和call来允许函数在调用时重新显式的指定this指针. func.call(object, arg ...