HDU1116(欧拉路径+并查集)
2024-08-30 15:46:19
题意:
给出一些字符串,有这两个字符串,如果第一个字符串的最后一个字母和第二个字符串的第一个字母是一样的,则这两个字符串是可以连接在一起的。
问给出的这些字符串能否串成一个环或者一整个链。
思路:
将头部看做是入度,将尾部看做是出度,如果是一个链的话那么
链的头部那个字母:indegree = outdegree+1;
链的尾部那个字母:indegree+1 = outdegree;
中间出现的字母:indegree = outdegree;
首先用并查集看看给出的这些链能不能连成一个连通分量,如果不是一个连通分量,那就一定不能连成一条链或者一个环。
然后根据欧拉路径(欧拉回路)的入度和出度的性质来判断。
欧拉路径:(百度百科)
代码:
#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <iomanip>
#define MAX 1000000000
#define inf 0x3f3f3f3f
#define FRE() freopen("in.txt","r",stdin) using namespace std;
typedef long long ll;
const int maxn = ;
int n;
int fa[],vis[],in[],out[];
char str[maxn]; int _find(int x)
{
return fa[x]==x ? x:fa[x] = _find(fa[x]);
} void init()
{
for(int i=; i<; i++)
{
fa[i] = i;
in[i] = out[i] = ;
vis[i] = ;
}
} int main()
{
//FRE();
int kase;
scanf("%d",&kase);
while(kase--)
{
init();
scanf("%d",&n);
for(int i=; i<n; i++)
{
scanf("%s",str);
int u = str[]-'a',v = str[strlen(str)-]-'a';
in[u]++;
out[v]++;
vis[u] = vis[v] = ;
u = _find(u);
v = _find(v);
if(u != v)
{ fa[u] = v; }
}
int a=,b=,c=,d=;
for(int i=; i<; i++)
{
if(vis[i] && fa[i]==i) { c++; }//首先得是一个连通分量才能连成一个环或者是一条链
if(vis[i])
{
if(in[i]==out[i]) continue;
else if(in[i]+==out[i]) a++;//尾部的字母
else if(in[i]==out[i]+) b++;//头部的字母
else d++;//中间不符合条件的情况
}
}
//cout<<a<<" "<<b<<" "<<c<<endl;
if(c> || d>) { puts("The door cannot be opened."); }
else if((a==&&b==) || (a==&&b==)) { puts("Ordering is possible."); }
else { puts("The door cannot be opened."); }
}
return ;
}
最新文章
- html5语义化标签使用规范
- 七天学会ASP.NET MVC (六)——线程问题、异常处理、自定义URL
- 22.整数二进制表示中1的个数[Get1BitCount]
- Verilog语法基础讲解之参数化设计
- KMP快速模式匹配的java实现
- 使用HISTCONTROL强制history忽略某条特定命令
- HTML5本地存储详解
- 经典.net面试题目(1)
- 【UWP】列表项宽度自适应的实现
- Spring中@Value标签的使用详解
- HTML中padding和margin的区别和用法
- 1.Linux下libevent和memcached安装
- 浅谈SnackBar(Toast大兄弟)
- 从零开始学Shell(一)
- terraform plugin 版本以及changlog 规范
- xcode 自动签名、手动签名
- NewEmployeesLearnNotes——新人程序员学习计划V1.1
- ie8下jquery改变PNG的opacity出现黑边
- HDU 6085 Rikka with Candies(bitset)
- html合并单元格