poj1386单词连接(欧拉欧拉欧拉)
2024-08-30 09:57:22
///单词连接,欧拉回路通路都可以(有向图)
///主要构图:比如possibilities就构造p->s的边
////题目大意:给你若干个字符串,一个单词的尾部和一个单词的头部相同那么这两个单词就可以相连,判断给出的n个单词是否能够一个接着一个全部连通。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=;
char s[];
int f[],outd[],ind[];
int find(int x){
return x==f[x]?x:f[x]=find(f[x]);
}
int main(){
int t;
scanf("%d",&t);
while(t--){
int n;
for(int i=;i<N;i++)
f[i]=i;
memset(outd,,sizeof(outd));
memset(ind,,sizeof(ind));
scanf("%d",&n);
while(n--){
scanf("%s",s);
int u=s[]-'a';
int v=s[strlen(s)-]-'a';
///u-->v
int a=find(u);
int b=find(v);
if(a!=b)
f[a]=b;
outd[u]++;
ind[v]++;
}
int flag=,sum=;
int sum_in=,sum_out=;
for(int i=;i<N;i++){
if(f[i]==i&&(outd[i]+ind[i])>)
sum++;
if(outd[i]!=ind[i]){
if(outd[i]+==ind[i])
sum_in++;
else if(outd[i]-==ind[i])
sum_out++;
else
flag=;
}
}
if(!flag&&sum==&&(sum_out==&&sum_in==||sum_in==&&sum_out==))
puts("Ordering is possible.");
else
puts("The door cannot be opened.");
}
return ;
}
最新文章
- Charles 如何抓取https数据包
- DOM对象 与 jQuery对象 之间的相互装换
- VIRTUALBOX 虚拟机安装 OS X 10.9 MAVERICKS
- form和validate示例
- Xmanager Enterprise 4 使用说明
- MySQL触发器 trigger之for each row
- flask 扩展之 -- flask-sqlalchemy
- C/C++ 知识点---排序实现
- Codeforces 858A. k-rounding 数论
- Bzoj 4950
- HDU 1043 Eight (BFS&;#183;八数码&;#183;康托展开)
- golang 内存模型
- Python-JSON和pickle
- 一JavaScript获取当前月份的前12个月,获取最近的12个月二js实现获取当前月份前的12个月份,格式化后放在一个数组里
- 给笔记本更换SSD硬盘
- MD5+Salt值
- Android打印当前所有线程及对应栈信息
- Qt中(图片)资源的使用方式
- Python3基础 list extend 合并列表
- 使用limma、Glimma和edgeR,RNA-seq数据分析易如反掌