题目:这里
题意:有一种由彩色珠子连接而成的项链,每个珠子两半由不同颜色(由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 ;
}
UVA 10054 (欧拉回路) The Necklace的更多相关文章
-
Uva 10054 欧拉回路 打印路径
看是否有欧拉回路 有的话打印路径 欧拉回路存在的条件: 如果是有向图的话 1.底图必须是连通图 2.最多有两个点的入度不等于出度 且一个点的入度=出度+1 一个点的入度=出度-1 如果是无向图的话 1 ...
-
UVA 10054 The Necklace(欧拉回路,打印路径)
题目链接: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem ...
-
uva 10054 The Necklace(欧拉回路)
The Necklace My little sister had a beautiful necklace made of colorful beads. Two successive beads ...
-
UVa 10054 The Necklace(无向图欧拉回路)
My little sister had a beautiful necklace made of colorful beads. Two successive beads in the neckla ...
-
UVA 10054 the necklace 欧拉回路
有n个珠子,每颗珠子有左右两边两种颜色,颜色有1~50种,问你能不能把这些珠子按照相接的地方颜色相同串成一个环. 可以认为有50个点,用n条边它们相连,问你能不能找出包含所有边的欧拉回路 首先判断是否 ...
-
UVa 10054 (打印欧拉回路) The Necklace
将每个颜色看成一个顶点,对于每个珠子在两个颜色之间连一条无向边,然后求欧拉回路. #include <cstdio> #include <cstring> + ; int G[ ...
-
uva 10054 The Necklace 拼项链 欧拉回路基础应用
昨天做了道水题,今天这题是比较水的应用. 给出n个项链的珠子,珠子的两端有两种颜色,项链上相邻的珠子要颜色匹配,判断能不能拼凑成一天项链. 是挺水的,但是一开始我把整个项链看成一个点,然后用dfs去找 ...
-
UVa 10054 The Necklace【欧拉回路】
题意:给出n个珠子,珠子颜色分为两半,分别用1到50之间的数字表示, 现在给出n个珠子分别的颜色,问是否能够串成一个环.即为首尾相连,成为一个回路 判断是否构成一个环,即判断是否为欧拉回路,只需要判断 ...
-
UVa 10054 The Necklace BFS+建模欧拉回路
算法指南 主要就是建立欧拉回路 #include <stdio.h> #include <string.h> #include <iostream> #includ ...
随机推荐
-
Spring学习记录(十三)---基于xml文件配置AOP
上一篇讲了用注解配置AOP,现在讲用xml怎么配置AOP 其实逻辑是一样的,只是用xml的方法,要把这种逻辑写出来,告诉spring框架去执行. 例子:这里的例子和上一篇的例子一样.换成xml方式 / ...
-
PHP 汉字拼音互转
<?PHP function Pinyin($_String, $_Code='gb2312'){ $_DataKey = "a|ai|an|ang|ao|ba|bai|ban|ban ...
-
PHP调用MYSQL存储过程实例
PHP调用MYSQL存储过程实例 标签: mysql存储phpsqlquerycmd 2010-09-26 11:10 11552人阅读 评论(3) 收藏 举报 实例一:无参的存储过程$conn = ...
-
Vijos1019 补丁VS错误[最短路 状态压缩]
描述 错误就是人们所说的Bug.用户在使用软件时总是希望其错误越少越好,最好是没有错误的.但是推出一个没有错误的软件几乎不可能,所以很多软件公司都在疯狂地发放补丁(有时这种补丁甚至是收费的).T公 ...
-
Laravel 安装predis 扩展
在安装predis扩展之前先安装composer,安装教程在https://getcomposer.org/download/: php -r "copy('https://getcompo ...
-
Unicode汉字编码表
U+ 0 1 2 3 4 5 6 7 8 9 A B C D E F ------------------------------------------ ...
-
Teach Yourself Scheme in Fixnum Days 13 Jump跳转
Jumps One of the signal features of Scheme is its support for jumps or nonlocal control. Specificall ...
-
Spring--------web应用中保存spring容器
---恢复内容开始--- 问题:在一个web应用中我使用了spring框架,但有一部分模块或组件并没有托管给Spring,比如有的可能是一个webservice服务类,如果我想在这些非托管的类里使用托 ...
-
IE的CSS滤镜不过只支持IE可以创建幻灯片等一些炫酷的效果
<img src="img/logo.png" style="filter:xray"/>仅仅
-
WPF实用小工具
Kaxaml 一款轻量级的Xaml代码编辑器,提供了可视的效果可以看到修改代码后的实时效果图.个人习惯于用它测试系统默认控件的行为和布局,小片段的xaml也可以拿到这个工具上测试效果.这款工具还提供了 ...