poj1386:http://poj.org/problem?id=1386
题意：给你n个单词，问你是否能够通过调整单词的顺序存在这样的一个序列，使得 每个单词的首字母是前一个单词的尾字母。
题解：每个单词可以看做从首字母连向尾字母的一条边，然后就是整个图的欧拉路径。统计每个点的入度和初度，如果基图连通，并且只有两个点入度和初度不等，并且相差分别为1，-1，就存在这样的路径，否则则没。 连通性，可以用并查集. 处理完之后，看每个点的父亲是否相等来判断是否连通。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
int in[], pa[], out[];// 统计入度，初读
bool used[];//记录出现过的字母
int n;//单词的个数
char str[];//读取单词
void UFset(){//初始化
for(int i=;i<=;i++){
used[i]=;
pa[i]=-;
out[i]=;
in[i]=;
}
}
int Find(int x){//查找
int s;
for(s=x;pa[s]>=;s=pa[s]);
while(s!=x){
int temp=pa[x];
pa[x]=s;
x=temp;
}
return s;
}
void Union(int R1,int R2){//合并
int r1=Find(R1);
int r2=Find(R2);
int temp=pa[r1]+pa[r2];
if(pa[r1]>pa[r2]){
pa[r1]=r2;
pa[r2]=temp;
}
else{
pa[r2]=r1;
pa[r1]=temp;
}
}
bool solve(){//判断连通性
int first=-;
for(int i=;i<=;i++){
if(!used[i])continue;
if(first==-)first=Find(i);
else if(first!=Find(i))return false;
}
return true;
}
int main(){
int cas;
scanf("%d",&cas);
while(cas--){
scanf("%d",&n);
UFset();
for(int i=;i<=n;i++){//建图
scanf("%s",str);
int len=strlen(str);
int u=str[]-'a'+;
int v=str[len-]-'a'+;
in[v]++;
used[v]=true;
out[u]++;used[u]=true;
if(Find(u)!=Find(v))
Union(u,v);
}
int one=,one1=;bool flag=true;
for(int j=;j<=;j++){
if(!used[j])continue;
if(out[j]-in[j]>=||in[j]-out[j]>=){
flag=false;
break;
}
if(out[j]-in[j]==){
one++;
if(one>)
{flag=false;break;}
}
if(out[j]-in[j]==-){
one1++;
if(one1>){
flag=false;break;
}
}
}
if(one!=one1)flag=false;
if(!solve())flag=false;
if(flag)printf("Ordering is possible.\n");
else
printf("The door cannot be opened.\n");
}
}
随机推荐
-
PHP问题Parse error: syntax error, unexpected end of file in
检查一下你的php文件中是否存在这样的语法错误:<<php{>或者<?{?>以上两种写法都是有错误的,修改为下面的就可以了: <?php}?>
-
Linux下Postfix的配置和使用
Postfix为何物,详见:http://zh.wikipedia.org/wiki/Postfix 0.关于Postfix postfix的产生是为了替代传统的sendmail.相较于sendmai ...
-
Phonegap(Cordova)3.4 + Android 环境搭建
PhoneGap是一个用基于HTML.CSS和JavaScript的,创建移动跨平台移动应用程序的高速开发平台. 它使开发人员可以利用iPhone,Android,WP7等多 ...
-
隐藏iframe边框
关于iframe在ie浏览器中边框隐藏的问题,一直困惑着我.其实就是一个很简单的办法,主要设置一个属性即可解决,方法如下: <iframe frameborder="0"&g ...
-
android开发之this.finish()的使用 分类： android 学习笔记 2015-07-18 19:05 30人阅读 评论(0) 收藏
在一个Activity用完之后应该将之finish掉,但是,之前在学校里自己摸索着开发时并没有太注意这个问题,因为activity无论是否finish掉对功能的影响貌似都不是那么明显(这是读书时候的观 ...
-
Oracle数据库管理员经常使用的表和视图
◆dba_开头 dba_users 数据库用户信息 dba_segments 表段信息 dba_extents 数据区信息 dba_objects 数据库对象信息 dba_tablespaces 数据 ...
-
Rouh set 入门知识1（基础定义篇）
粗糙集理论是继概率论.模糊集.证据论后又一处理不完整性和不确定性的数学工具,建立在分类机制的基础上.无需提供问题所处理的数据集合之外的任何先验信息条件.并且能有效分析不精确.不一致.不完整等各种不完备 ...
-
Less 关于css hack的写法
由于工作需要,最近一直在弄css转写less,遇到最多的问题就是 hack的写法,一些IE的hack,less不支持编译: 常见的不支持的hack如下: IE的滤镜写法 \9\0 IE8部分支持 ...
-
MVC ViewData和ViewBag
视图数据可以通过ViewBag属性访问,它主要是为了从Controller到view进行传值用的,类似有所使用的ViewData[] 字典类.对于ViewBag是如此的强大,意味着你能动态的s ...
-
详细查看数据库SQL执行计划
DBCC DROPCLEANBUFFERS 清除数据缓存DBCC FREEPROCCACHE 清除执行计划缓存 SET SHOWPLAN_XML ON 此语句导致 SQL Server 不执行 Tr ...