欧拉路径是指能从一个点出发能够“一笔画”完整张图的路径;(每条边只经过一次而不是点)
在无向图中:如果每个点的度都为偶数 那么这个图是欧拉回路;如果最多有2个奇数点,那么出发点和到达点必定为
该2点,那么这个路径就为欧拉路;(前提都是该图连通)
在有向图中:如果每个店的出度和入度都相同,那么为欧拉回路;如果最多只能有2个点的出度不等于入度,并且其中
一个点的 入度=出度+1,另一点的 入度+1=出度,那么为欧拉路;(前提图连通)

//因为字符从第一个到最后一个,所以用有向图
#include<stdio.h>
#include<string.h>
#include<stack>
using namespace std;
char ch[];
int map[][],n,m,pa[];
int r[],c[],vis[];
stack<int>s;
void inint()
{
  int i;
  for(i=;i<=;i++)
  {
    pa[i]=i;
  }
}
int find(int x)
{
  if(x!=pa[x])
    pa[x]=find(pa[x]);
  return pa[x];
}
int main()
{
  int i,j;
  int t;
  scanf("%d",&t);
  while(t--)
  {
    scanf("%d",&m);
    memset(vis,,sizeof(vis));
    inint();
    memset(r,,sizeof(r));
    memset(c,,sizeof(c));
    memset(map,,sizeof(map));
    for(i=;i<m;i++)
    {
      scanf("%s",&ch);
      int l=strlen(ch);
      map[ch[]-'a'+][ch[l-]-'a'+]=;
      r[ch[]-'a'+]++;c[ch[l-]-'a'+]++;
      int x,y;
      x=find(ch[]-'a'+);
      y=find(ch[l-]-'a'+);
      vis[ch[]-'a'+]=;
      vis[ch[l-]-'a'+]=;
      if(x!=y)
        pa[x]=y;
    }
    int sum=;
    for(i=;i<=;i++)
    {
      if(pa[i]==i&&vis[i])
      {
        sum++;
      }
      if(sum>)
        break;
    }
    if(sum>) //未连通
    {
      printf("The door cannot be opened.\n");
      continue;
    }
    sum=;
    for(i=;i<=;i++)
    {
      if(vis[i]&&(c[i]!=r[i]))//寻找出度入度不相同的点
      {
        sum++;
        s.push(i);
      }
    }
    if(sum>)//多余2个
      printf("The door cannot be opened.\n");
    else if(sum==)//出度入度全相同
      printf("Ordering is possible.\n");
    else if(sum==)
    {
      int x1,x2;
      x1=s.top();
      s.pop();
      x2=s.top();
      s.pop();
      if((c[x1]+==r[x1])&&(c[x2]==r[x2]+)||(c[x2]+==r[x2])&&(c[x1]==r[x1]+))//判断是否条件成立
      {
        printf("Ordering is possible.\n");
      }
      else printf("The door cannot be opened.\n");
    }
    else
      printf("Ordering is possible.\n");
  }
}

最新文章

  1. 3-linux下部署tomcat应用
  2. 将Web站点由IIS6迁移至IIS7
  3. 关于tomcat小知识
  4. GDB打印STL容器内容
  5. (剑指Offer)面试题21:包含min函数的栈
  6. 状态模式(State Pattern)
  7. [C++关键字] alignof &amp; alignas 内存对齐 sizeof 占内存大小
  8. Android 开源项目 eoe 社区 Android 客户端(转)
  9. mybati的存储过程
  10. Deep Learning论文笔记之(六)Multi-Stage多级架构分析
  11. JVM类加载原理学习笔记
  12. js和css实现手机横竖屏预览思路整理
  13. jQuery实现购物车物品数量的加减
  14. 使用iostat来对linux硬盘IO性能进行检测
  15. 深度学习Bible学习笔记:第六章 深度前馈网络
  16. spring的bean在什么时候被实例化
  17. 解决代码报红:Cannot resolve symbol &#39;xxx&#39;
  18. 两个docker容器互连时,提示no route to host错误的问题
  19. [javascript] Promise简单学习使用
  20. spider-抓取页面内容

热门文章

  1. NOIP2000进制转换
  2. SQL各种语句、函数
  3. PHP中文名文件下载实现
  4. MVC编写的新闻页面
  5. 获取assemblies信息in .net core
  6. JAVA常用的XML解析方法
  7. 升级nodejs版本
  8. 洛谷 1016 / codevs 1046 旅行家的预算
  9. XmlSpy / XSD 以及 验证
  10. Logging的这点小事