poj 1386 Play on Words (欧拉路)
题意：n个单词，问能否形成一个串（单词接龙，收尾相连，当且仅当前一个单词的末尾字母和后一个单词的首字母相同）
思路：欧拉路。
关于欧拉路：
(1)**有向图G为欧拉图(存在欧拉回路)，当且仅当G的基图连通（弱联通，），且所有顶点的入度等于出度。**(2)有向图G为半欧拉图(存在欧拉路)，当且仅当G的基图连通（弱联通），且存在顶点u的入度比出度大1、v的入度比出度小1，其它所有顶点的入度等于出度。
（3） 无向图存在欧拉回路: 图连通，所有点都是偶数度，
（4）无向图存在欧拉路：图联通，只有两个点的度数为奇数。
有向图判断联通性判断的弱联通，因此可以用并查集实现。
具体办法是，判断根的个数，个数为大于1表示不联通。
#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;
}
** **