欧拉回路,利用并查集来实现;

代码:

#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
int a[],f[],b[];
bool vis[]; int find(int x)
{
return f[x]==-?x:f[x]=find(f[x]);
} void combine(int x,int y)
{
int n=find(x);
int m=find(y);
if(n!=m) f[n]=m;
} bool oula()
{
int st=-;
for(int i=; i<; i++)
{
if(a[i]||b[i])
if(st==-)st=find(i);
else if(st!=find(i)) return false;
}
vector<int>v;
for(int i=; i<; i++)
if(a[i]!=b[i])
v.push_back(a[i]-b[i]);
return v.size()==||v.size()==&&v[]*v[]==-;
} int main()
{
int t,n;
char s[];
scanf("%d",&t);
while(t--)
{
memset(a,,sizeof a);
memset(f,-,sizeof f);
memset(b,,sizeof b);
int ans=,cnt=;
bool flag=;
scanf("%d",&n);
for(int i=; i<n; i++)
{
scanf("%s",&s);
int l=strlen(s);
int x=s[]-'a',y=s[l-]-'a';
a[x]++,b[y]++;
combine(x,y);
}
if(oula()) printf("Ordering is possible.\n");
else puts("The door cannot be opened.");
}
return ;
}

最新文章

  1. hdu 5587 Array
  2. MYSQL-用户权限的验证过程
  3. Java集合框架面试题
  4. js闭包的产生
  5. Sharepoint2010突然之间不能打开页面,报503错误The service is unavailable
  6. python(13)线程池:threading
  7. Mammoth官方文档翻译
  8. webservice底层使用Socket进行网络调用
  9. Oracle新建用户赋只读某几张表的权限
  10. HTA基础
  11. 窥探ASP.Net MVC底层原理 实现跨越Session的分布式TempData
  12. Confluence 6 识别慢性能的宏
  13. 2015-10-07 jQuery2
  14. IntelliJ IDEA 2017.3/2018.1激活与汉化
  15. 适配手机端之 rem
  16. 公网Ip和私网ip
  17. Codeforces Round #372 (Div. 1) A. Plus and Square Root 数学题
  18. OPC UA
  19. BZOJ 1015: [JSOI2008]星球大战starwar(并查集求连通块+离线处理)
  20. UVA-10995 Educational Journey

热门文章

  1. java coding recommand
  2. C++ notes for beginners
  3. ubuntu系统安装redis
  4. 史上最全的JavaScript工作笔记
  5. jBPM开发入门指南
  6. Spring、struts、webwork2三者MVC的比较
  7. linux下神奇的script命令
  8. OC - 12.NSURLRequest与NSURLConnection
  9. PAT_1007 素数对猜想
  10. ZeroBrane Lua脚本编辑器代码自动补全