poj 1386 Play on Words (欧拉路)

poj 1386

题意：n个单词，问能否形成一个串（单词接龙，收尾相连，当且仅当前一个单词的末尾字母和后一个单词的首字母相同）

思路：欧拉路。

关于欧拉路：

(1)有向图G为欧拉图(存在欧拉回路)，当且仅当G的基图连通（弱联通，），且所有顶点的入度等于出度。

(2)有向图G为半欧拉图(存在欧拉路)，当且仅当G的基图连通（弱联通），且存在顶点u的入度比出度大1、v的入度比出度小1，其它所有顶点的入度等于出度。

（3） 无向图存在欧拉回路:  图连通，所有点都是偶数度，

（4）无向图存在欧拉路：图联通，只有两个点的度数为奇数。

有向图判断联通性判断的弱联通，因此可以用并查集实现。

具体办法是，判断根的个数，个数为大于1表示不联通。

 

C++
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;
}
 
 
 
 

 

 

 

 

 

 

作者： CrazyKK

ex-ACMer@hust，stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人！

提醒
wpDiscuz