题目:这里

题意:有一种由彩色珠子连接而成的项链,每个珠子两半由不同颜色(由1到50的数字表示颜色)组成,相邻的两个珠子在接触的地方颜色相同,现在有一些零碎的珠子,确认它是否能

复原成完整的项链。

把每种颜色看成一个结点,每个珠子的两半连成一条有向边,就成了判断一个欧拉回路了,而输出回路路线可以用dfs,逆序输出,因为顺序输出的时候,由于可能会有一个结点上多

条边的情况,dfs的时候可能一开始会找到错误的路线再回溯回去,顺序输出就把这段错误的路线也输出了。

 #include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std; const int M = 1e3 + ;
int cas,head[M*],father[],du[];
int vis[][]; struct Edge{
int next,to;
}edge[M*]; int findest(int x)
{
if (x==father[x]) return x;
father[x]=findest(father[x]);
return father[x];
} void add(int v,int u)
{
edge[++cas].next=head[v];
edge[cas].to=u;
head[v]=cas;
} void euler(int u)
{
for (int i=head[u] ; i ; i=edge[i].next){
int v=edge[i].to;
if (!vis[u][v]) continue;
vis[u][v]--;vis[v][u]--;
euler(edge[i].to);
printf("%d %d\n",v,u);
}
} int main()
{
int t,tem=;
scanf("%d",&t);
int e=t;
while (t--)
{
int n,w;cas=;
scanf("%d",&n);
memset(du,,sizeof(du));
memset(vis,,sizeof(vis));
memset(head,,sizeof(head));
for (int i= ; i<= ; i++) father[i]=i;
for (int i= ; i<=n ; i++) {
int l,r;
scanf("%d%d",&l,&r);
if (i==) w=l;
du[l]++;du[r]++;
add(l,r);
add(r,l);
vis[l][r]++;vis[r][l]++;
int x=findest(l),y=findest(r);
if (x!=y) father[x]=y;
}
bool flag=false;
int x=findest(w);
for (int i= ; i<= ; i++){
if (du[i]==) continue;
if (du[i]%!=) flag=true;
if (findest(i)!=x) flag=true;
if (flag) break;
}
cas=;
if (tem!=) printf("\n");
printf("Case #%d\n",++tem);
if (flag) puts("some beads may be lost");
else euler(w);
}
return ;
}

最新文章

  1. ASP.NET Aries 入门开发教程8:树型列表及自定义右键菜单
  2. 项目中Ajax调用ashx页面中的Function的实战
  3. cf158B(水题)
  4. Java多线程概述
  5. 使用ROW_NUMBER进行的快速分页
  6. Jsp的九个隐含对象
  7. Android下pm 命令详解
  8. javascript写贪吃蛇游戏(20行代码!)
  9. 工作中git 操作汇总
  10. “茴”字有四种写法,this也是一样
  11. jQuery的一生
  12. 电信项目java补充类
  13. hadoop安装hive及java调用hive
  14. Linux文件下载(转)
  15. iPhone开发之使用NSUserDefaults存储数据
  16. Hadoop生态集群hdfs原理(转)
  17. 20155339 Exp3 免杀原理与实践
  18. HBase 负载均衡
  19. Python3.4下使用sqlalchemy
  20. 【Codeforces 506E】Mr.Kitayuta’s Gift&amp;&amp;【BZOJ 4214】黄昏下的礼物 dp转有限状态自动机+矩阵乘法优化

热门文章

  1. ajax通讯之格式详解
  2. osx 编译安装配置 ruby on rails
  3. 易语言5.6 精简破解版[Ctoo]
  4. 客户端挂载NFS服务器中的共享目录(用户后台上传图片与前台上传图片放在同一个服务器上)
  5. Python自动化 【第十八篇】:JavaScript 正则表达式及Django初识
  6. 编译安装php
  7. JS学习之路(这个觉得写的很好,放在这里是方便查看)
  8. 安装mysql 5.7+版本缺少data文件夹
  9. js判断input输入框长度(支持中英文输入)
  10. 第五章 征服数据库(Spring对DB的使用)——开发持久层