uva10129 PlayOnWords(并查集,欧拉回路)
2024-08-24 22:48:51
判断无向图是否存在欧拉回路,就是看度数为奇数的点有多少个,如果有两个,那么以那分别两个点为起点和终点,可以构造出一条欧拉回路,如果没有,就任意来,否则,欧拉回路不存在。
首先用并查集判断连通,然后统计度数。
#include<cstdio>
#include<cstring>
#include<vector>
//#include<algorithm>
//#define local
using namespace std; const int maxl = ;
const int maxn = 1e3 + ;
int p[maxl];
bool used[maxl];//出现过的字符 char s[maxn]; int Find(int x) {return p[x] == x ? x : p[x] = Find(p[x]); } char last(char *p)
{
while(*(++p));
return *(p-);
} int deg[maxl];//出度 - 入度
#define ID(c) (c-'a')
int main()
{
#ifdef local
freopen("in10129.txt","r",stdin);
#endif // local
int T,N;
scanf("%d",&T);
while(T--) {
memset(used,false,sizeof(used));
memset(deg,,sizeof(deg));
int cc = ;
for(int i = ; i < maxl; i ++) { p[i] = i; }
scanf("%d", &N);
while(N--){
scanf("%s",s);
int u = ID(*s), v = ID(last(s));
deg[u]++; deg[v]--;
used[u] = used[v] = true;
int s1 = Find(u), s2 = Find(v);
if(s1 != s2) {
p[s1] = s2; cc--;
}
}
bool ok = false;
for(int i = ; i < maxl; i ++) {
if(!used[i]) cc--;
}
int odd[maxl] = {},top = ;
if(cc == ){
for(int i = ; i < maxl; i ++) if(deg[i]) {
odd[top++] = deg[i];
}
if(top == && (odd[] == || odd[] == ) ) ok = true;//入度sum = 出度sum
else if(top == ) ok = true;
}
if(ok) printf("Ordering is possible.\n");
else printf("The door cannot be opened.\n");
}
return ;
}
最新文章
- Account Team使用说明
- 伯克利包过滤(Berkeley Packet Filter,BPF)语言
- Delphi 字符数组存入文件
- android 事件处理概念簇
- .net学习笔记----Asp.net的生命周期之一应用程序生命周期
- 第一个Sprint冲刺第三天
- angularjs $watch demo
- ECSHOP在线手册之模板结构说明 (适用版本v2.7.3)
- 高质量PHP代码的50个实用技巧必备(上)
- Android 6.0出现的init: cannot execve(‘XXX’):Permission denied问题:禁止SELINUX的权限设置
- WPF使用CefSharp嵌入网页
- 移动端web开发的注意点大总结
- Android-Nexus5-命令刷机
- java使用RunTime调用windows命令行
- 爬虫----模拟用户登录gitHub
- MQTT协议
- BZOJ1552[Cerc2007]robotic sort&;BZOJ3506[Cqoi2014]排序机械臂——非旋转treap
- Selenium基础知识(九)验证码
- jquery事件及插件
- SpringBoot2 【关于:Table &#39;XXX.hibernate_sequence&#39; doesn&#39;t exist】