//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 欧拉回路的更多相关文章
-
hdu-1116(欧拉回路+并查集)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1116 思路:将字符串的头元素和尾元素视为图的x,y节点,然后合并x,y. 如果这个图不连通,则门不能打 ...
-
ACM/ICPC 之 混合图的欧拉回路判定-网络流(POJ1637)
//网络流判定混合图欧拉回路 //通过网络流使得各点的出入度相同则possible,否则impossible //残留网络的权值为可改变方向的次数,即n个双向边则有n次 //Time:157Ms Me ...
-
[poj2337]求字典序最小欧拉回路
注意:找出一条欧拉回路,与判定这个图能不能一笔联通...是不同的概念 c++奇怪的编译规则...生不如死啊... string怎么用啊...cincout来救? 可以直接.length()我也是长见识 ...
-
ACM: FZU 2112 Tickets - 欧拉回路 - 并查集
FZU 2112 Tickets Time Limit:3000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u P ...
-
UVA 10054 the necklace 欧拉回路
有n个珠子,每颗珠子有左右两边两种颜色,颜色有1~50种,问你能不能把这些珠子按照相接的地方颜色相同串成一个环. 可以认为有50个点,用n条边它们相连,问你能不能找出包含所有边的欧拉回路 首先判断是否 ...
-
POJ 1637 混合图的欧拉回路判定
题意:一张混合图,判断是否存在欧拉回路. 分析参考: 混合图(既有有向边又有无向边的图)中欧拉环.欧拉路径的判定需要借助网络流! (1)欧拉环的判定:一开始当然是判断原图的基图是否连通,若不连通则一定 ...
-
codeforces 723E (欧拉回路)
Problem One-Way Reform 题目大意 给一张n个点,m条边的无向图,要求给每条边定一个方向,使得最多的点入度等于出度,要求输出方案. 解题分析 最多点的数量就是入度为偶数的点. 将入 ...
-
UVa 12118 检查员的难题(dfs+欧拉回路)
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem& ...
-
UVA 10054 (欧拉回路) The Necklace
题目:这里 题意:有一种由彩色珠子连接而成的项链,每个珠子两半由不同颜色(由1到50的数字表示颜色)组成,相邻的两个珠子在接触的地方颜色相同,现在有一些零碎的珠子,确认它是否能 复原成完整的项链. 把 ...
随机推荐
-
wikioi 1204 寻找子串位置
/*======================================================================== 1204 寻找子串位置 题目描述 Descript ...
-
libevent简单介绍
http://blog.csdn.net/mafuli007/article/details/7476014 1 简介 主页:http://www.monkey.org/~provos/li ...
-
关于“学习Linux用什么系统”的解答
首先,阐述一下,我个人的观点——这个问题我曾经也想了很久了,这绝不是长篇大论后就是简单一句,适合你的就是最好的.其实,很多人看到这一句,心里已经有成千上万个奔腾了(至少我当时是这样的),为什么?因为我 ...
-
[Falcor] Intro to JSON Graph
JSON is a very commonly used data interchange format. Unfortunately while most application domain mo ...
-
Android CursorAdapter
CursorAdapter 继承于BaseAdapter是个虚类,它为cursor和ListView提供了连接的桥梁. public abstract class Cur ...
-
【Codeforces Round】 #431 (Div. 2) 题解
Codeforces Round #431 (Div. 2) A. Odds and Ends time limit per test 1 second memory limit per test ...
-
jedis单机版应用
1.pom文件添加依赖: 2.创建配置文件 创建单机版redisClient 代码: package com.skymall.rest.dao.imp; import org.springframew ...
-
kettle的下载、安装和初步使用(windows平台下)(图文详解)
kettle的下载 Kettle可以在http://kettle.pentaho.org/网站下载 http://sourceforge.net/projects ...
-
前端获取的数据是undefined
var id = $("id1").val(); var username = $("username1").val(); var password = $(& ...
-
RHEL7 在不同的环境中使用不同的网络配置文件
比如,我们可以设置RHEL7 系统在公司时使用一个网卡配置文件:在家时则使用另外一个配置文件(可以根据不同的环境设置多个网卡配置文件). 网卡配置信息如下: [root@rhel7 ~]# nmcli ...