hdu1116 欧拉回路

时间:2022-12-19 22:06:04
 //Accepted    248 KB    125 ms
 //欧拉回路
 //以26个字母为定点,一个单词为从首字母到末尾字母的一条边
 //下面就是有向图判断欧拉回路
 //连通+节点入度和==出度和 或者 存在一对节点一个入度比出度大1,一个小1
 #include <cstdio>
 #include <cstring>
 #include <iostream>
 #include <queue>
 using namespace std;
 ;
 int a[imax_n][imax_n];
 bool used[imax_n];
 bool vis[imax_n];
 int cnt_in[imax_n],cnt_out[imax_n];
 int n;
 ];
 queue<int >q;
 void bfs(int s)
 {
     while (!q.empty()) q.pop();
     //if (used[s]==0) return 0;
     q.push(s);
     vis[s]=;
     while (!q.empty())
     {
         int x=q.front();
         q.pop();
         ;i<imax_n;i++)
         {
              && !vis[i] && a[x][i])
             {
                 vis[i]=;
                 q.push(i);
             }
         }
     }
 }
 bool judge()
 {
     int flag;
     ;i<=;i++)
     {
         memset(vis,,sizeof(vis));
         bfs(i);
         flag=;
         ;j<=;j++)
          && !vis[j]) flag=;
         ) ;
     }
     ;
 }
 bool slove()
 {
     int p,ne;
     p=ne=;
     ;i<=;i++)
     {
         int t=cnt_in[i]-cnt_out[i];
         ) continue;
         )
         {
             p++;
             ) ;
             continue;
         }
         )
         {
             ne++;
             ) ;
             continue;
         }
         ;
     }
      && ne== || p== && ne==)) ;
     ;
 }
 int main()
 {
     int T;
     scanf("%d",&T);
     while (T--)
     {
         scanf("%d",&n);
         int x,y;
         memset(a,,sizeof(a));
         memset(used,,sizeof(used));
         memset(cnt_in,,sizeof(cnt_in));
         memset(cnt_out,,sizeof(cnt_out));
         ;i<n;i++)
         {
             scanf("%s",s);
             int l=strlen(s);
             x=s[]-;
             y=s[l-]-;
             used[s[]-]=true;
             used[s[l-]-]=true;
             a[x][y]=;
             cnt_out[x]++;
             cnt_in[y]++;
         }
          && slove()==)
         printf("Ordering is possible.\n");
         else
         printf("The door cannot be opened.\n");
     }
     ;
 }

hdu1116 欧拉回路的更多相关文章

  1. hdu-1116(欧拉回路&plus;并查集)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1116 思路:将字符串的头元素和尾元素视为图的x,y节点,然后合并x,y. 如果这个图不连通,则门不能打 ...

  2. ACM&sol;ICPC 之 混合图的欧拉回路判定-网络流&lpar;POJ1637&rpar;

    //网络流判定混合图欧拉回路 //通过网络流使得各点的出入度相同则possible,否则impossible //残留网络的权值为可改变方向的次数,即n个双向边则有n次 //Time:157Ms Me ...

  3. &lbrack;poj2337&rsqb;求字典序最小欧拉回路

    注意:找出一条欧拉回路,与判定这个图能不能一笔联通...是不同的概念 c++奇怪的编译规则...生不如死啊... string怎么用啊...cincout来救? 可以直接.length()我也是长见识 ...

  4. ACM&colon; FZU 2112 Tickets - 欧拉回路 - 并查集

     FZU 2112 Tickets Time Limit:3000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u P ...

  5. UVA 10054 the necklace 欧拉回路

    有n个珠子,每颗珠子有左右两边两种颜色,颜色有1~50种,问你能不能把这些珠子按照相接的地方颜色相同串成一个环. 可以认为有50个点,用n条边它们相连,问你能不能找出包含所有边的欧拉回路 首先判断是否 ...

  6. POJ 1637 混合图的欧拉回路判定

    题意:一张混合图,判断是否存在欧拉回路. 分析参考: 混合图(既有有向边又有无向边的图)中欧拉环.欧拉路径的判定需要借助网络流! (1)欧拉环的判定:一开始当然是判断原图的基图是否连通,若不连通则一定 ...

  7. codeforces 723E (欧拉回路)

    Problem One-Way Reform 题目大意 给一张n个点,m条边的无向图,要求给每条边定一个方向,使得最多的点入度等于出度,要求输出方案. 解题分析 最多点的数量就是入度为偶数的点. 将入 ...

  8. UVa 12118 检查员的难题(dfs&plus;欧拉回路)

    https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem& ...

  9. UVA 10054 &lpar;欧拉回路&rpar; The Necklace

    题目:这里 题意:有一种由彩色珠子连接而成的项链,每个珠子两半由不同颜色(由1到50的数字表示颜色)组成,相邻的两个珠子在接触的地方颜色相同,现在有一些零碎的珠子,确认它是否能 复原成完整的项链. 把 ...

随机推荐

  1. wikioi 1204 寻找子串位置

    /*======================================================================== 1204 寻找子串位置 题目描述 Descript ...

  2. libevent简单介绍

    http://blog.csdn.net/mafuli007/article/details/7476014 1      简介 主页:http://www.monkey.org/~provos/li ...

  3. 关于&OpenCurlyDoubleQuote;学习Linux用什么系统”的解答

    首先,阐述一下,我个人的观点——这个问题我曾经也想了很久了,这绝不是长篇大论后就是简单一句,适合你的就是最好的.其实,很多人看到这一句,心里已经有成千上万个奔腾了(至少我当时是这样的),为什么?因为我 ...

  4. &lbrack;Falcor&rsqb; Intro to JSON Graph

    JSON is a very commonly used data interchange format. Unfortunately while most application domain mo ...

  5. Android CursorAdapter

    CursorAdapter 继承于BaseAdapter是个虚类,它为cursor和ListView提供了连接的桥梁.            public abstract class     Cur ...

  6. 【Codeforces Round】 &num;431 &lpar;Div&period; 2&rpar; 题解

    Codeforces Round #431 (Div. 2)  A. Odds and Ends time limit per test 1 second memory limit per test ...

  7. jedis单机版应用

    1.pom文件添加依赖: 2.创建配置文件 创建单机版redisClient 代码: package com.skymall.rest.dao.imp; import org.springframew ...

  8. kettle的下载、安装和初步使用(windows平台下)(图文详解)

    kettle的下载 žKettle可以在http://kettle.pentaho.org/网站下载                   http://sourceforge.net/projects ...

  9. 前端获取的数据是undefined

    var id = $("id1").val(); var username = $("username1").val(); var password = $(& ...

  10. RHEL7 在不同的环境中使用不同的网络配置文件

    比如,我们可以设置RHEL7 系统在公司时使用一个网卡配置文件:在家时则使用另外一个配置文件(可以根据不同的环境设置多个网卡配置文件). 网卡配置信息如下: [root@rhel7 ~]# nmcli ...