题意：n个单词，问能否形成一个串（单词接龙，收尾相连，当且仅当前一个单词的末尾字母和后一个单词的首字母相同）
思路：欧拉路。
关于欧拉路：
(1)有向图G为欧拉图(存在欧拉回路)，当且仅当G的基图连通（弱联通，），且所有顶点的入度等于出度。
(2)有向图G为半欧拉图(存在欧拉路)，当且仅当G的基图连通（弱联通），且存在顶点u的入度比出度大1、v的入度比出度小1，其它所有顶点的入度等于出度。
（3） 无向图存在欧拉回路: 图连通，所有点都是偶数度，
（4）无向图存在欧拉路：图联通，只有两个点的度数为奇数。
有向图判断联通性判断的弱联通，因此可以用并查集实现。
具体办法是，判断根的个数，个数为大于1表示不联通。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 |
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <cstdlib> #include <ctime> #define fst first #define sec second #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define ms(a,x) memset(a,x,sizeof(a)) typedef long long LL; #define pi pair < int ,int > #define MP make_pair using namespace std; const double eps = 1E-8; const int dx4[4]={1,0,0,-1}; const int dy4[4]={0,-1,1,0}; const int inf = 0x3f3f3f3f; const int N=26; int in[N]; int out[N]; int f[N]; int root ( int x) { if (x!=f[x]) f[x] = root(f[x]); return f[x]; } void merge( int x,int y) { int rx = root(x); int ry = root(y); if (rx!=ry) f[rx] = ry; } void init() { for ( int i = 0 ; i < N ; i++) f[i] = i; ms(in,0); ms(out,0); } int n ; set<int>se; bool Euler() { int a,b; a=b=0; set<int>::iterator it; for ( it = se.begin() ;it!=se.end() ; it++) { int i = *it; if (in[i]==out[i]+1)a++; else if (out[i]==in[i]+1) b++; else if (out[i]!=in[i]) return false; } if (a+b==0||(a==1&&b==1)) return true; return false; } int main() { #ifndef ONLINE_JUDGE freopen("code/in.txt","r",stdin); #endif int T; cin>>T; while (T--) { init(); scanf("%d",&n); se.clear(); for ( int i = 0 ; i < n ; i++) { char st[1005]; scanf("%s",st); int len = strlen(st); int u = st[0]-'a'; int v = st[len-1]-'a'; merge(u,v); out[u]++; in[v]++; se.insert(v); se.insert(u); } int cnt = 0 ; bool die = false; for (set<int>::iterator it = se.begin() ; it!=se.end() ; it++) { if (f[*it]==*it) cnt++; if (cnt>1) { die = true; break; } } if (!Euler()) die = true; if (die) { puts("The door cannot be opened."); } else { puts("Ordering is possible."); } } #ifndef ONLINE_JUDGE fclose(stdin); #endif return 0; } |
说点什么
您将是第一位评论人！