/*
有向欧拉图问题,刘汝佳p112页有详细说明
使用并查集来判断图是否连通,并判断入度和出度情况
题意:将门上的单词最后都拼接在一起,
其中前一个单词的最后一个字母必须和后一个单词的第一个字母相同
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
using namespace std;
const int nMax=30;
//degree
int indgr[nMax],outdgr[nMax],p[nMax];
int find(int x)
{
return p[x]==x?x:p[x]=find(p[x]);
}
int main()
{
//freopen("data.in","r",stdin);
int T,N;
scanf("%d",&T);
while(T--)
{
memset(indgr,0,sizeof(indgr));
memset(outdgr,0,sizeof(outdgr));
for(int i=0;i<26;i++)
p[i]=i;
scanf("%d",&N);
for(int i=0;i<N;i++)
{
string str;
cin>>str;
int a=str[0]-'a';
int b=str[str.size()-1]-'a';
indgr[b]++;
outdgr[a]++;
if(find(a)!=find(b))
p[find(a)]=find(b);
}
bool ok=true;
int u;
for(u=0;!indgr[u] && !outdgr[u];u++);
for(int i=u+1;i<26;i++)
if((indgr[i] || outdgr[i]) && find(u)!=find(i))
{
ok=false;
break;
}
if(ok)
{
int in_num=0,out_num=0;
for(int i=0;i<26;i++)
{
if(indgr[i]>outdgr[i])
{
if(indgr[i]==outdgr[i]+1)
in_num++;
else
{
ok=false;
break;
}
}
else if(outdgr[i]>indgr[i])
{
if(outdgr[i]==indgr[i]+1)
out_num++;
else
{
ok=false;
break;
}
}
}
if(in_num>1 || out_num>1)//在这里WA了N多次,出错原因,漏掉了in_num和out_num都为零的那种情况
ok=false;
}
if(ok)
printf("Ordering is possible.\n");
else
printf("The door cannot be opened.\n");
}
return 0;
}
分享到:
相关推荐
1. 了解欧拉图的来历、定义以及图论表述 2. 能快速写出求最短路的最小插点问题的动态规划算法 1. 写出判定一个给定的图是否是欧拉图的算法 2. 写出寻找含有
大数据-算法
欧拉图及其相关问题
欧拉图的构造算法 欧拉图的构造 构造欧拉图算法
图论及其算法-2欧拉图与哈密尔顿图.ppt
离散数学上机作业:用C或者C++实现欧拉图算法
实验内容: 对具有n个结点的无向图,判断其能否被一笔画。 实验要求: 对给定n个结点的无向图,进行欧拉图和半欧拉图的判定,若是欧拉图或半欧拉图,则输出所有的欧拉(回)路。
用C语言实现对欧拉图的判定,主要分为两个部分:判断每个顶点的度是否为偶数、判断图是否连通。其中,对图连通性的判定使用了Warshall算法。
提出了2种赋予任意一个图均衡方向的方法:欧拉图构造法和圈树分解法,第一种方法是欧拉图构造法:若给定的图是欧拉图,先找到欧拉环游后再顺着欧拉环游的方向给边赋予方向,若不是欧拉图,可以通过给此非欧拉图补充边得到...
逻辑学欧拉图试题(卷)与答案解析.doc
欧拉图与相关专题 出版时间:2012年版 内容简介 《现代数学译丛(21):欧拉图与相关专题》是迄今为止唯一的一本全面阐述欧拉图理论的主要研究成果和研究方法及其与其他图论问题之间的联系的专著。本书包含两卷共...
本代码是一个关于欧拉图的随机生成,欧拉图判定,欧拉图遍历的一个可视化的小软件。可以用来进行简单的欧拉图研究。该代码运用MFC和常用算法,来实现所求功能。本代码可用于教学、科学研究、基础代码应用等。
许智磊 -《浅谈补集转化思想在统计问题中的应用》 张 宁 -《猜数问题的研究》 张云亮 -《论对算法的选择》 周 源 -《浅析"最小表示法"思想在字符串循环同构问题中的应用》 ## 2004 何 林 -《信息学中守恒法...
有欧拉图与汉密尔顿图的概念与应用 以及他们的判定定理
哈密顿图和欧拉图的判断毕业设计源代码 虽然很简单,但是没有认真学习过要编程实现的话还是挺麻烦的
离散欧拉图.exe
运用点回路与变回路的方法来判断哈密顿图与欧拉图。推荐
里面有四个代码,分别是真值表的判断,并交差集、判断二元关系、判断欧拉图;每个代码的具体功能实现是分开方法写的,读者可以快速知道某个功能的具体实现方式
欧拉图matlab代码Staver-Levin模型的概率基础 用于从我们的论文中产生图形的MATLAB脚本- 图2 particle_system_bifurcation_diagram.m 图3 QSD_final.m 吸收率 图4 Poisson_full_model.m ODE_euler_scheme.m 图5...