此页面通过工具从 csdn 导出，格式可能有问题。
好久不写代码果然手会生成屎
题目在 poj上也有
题意就是给你一堆单词，按首位顺序排列起来，问你有没有解。
第一眼看上去是个哈密顿通路，单词当做节点，首尾关系作边，听上去妥妥的不过N有100000 复杂度太恐怖。
其实是从刘汝佳的小白书第二版（其实该叫小紫红书了）上欧拉回路那节看到的，所以得考虑考虑转换
把单词当边，首尾字符当做点 题目就转变为 欧拉通路
不得不感慨，图论算法的重点还是在构图！！！
判断欧拉通路：
1. 一个有向图存在欧拉回路必定也存在欧拉通路...因为通路的定义包括了回路
2. 不考虑为欧拉回路的情况..一个有向图是欧拉通路就必须有一个点出度-入度=1,一个点入度-出度=1..这两点就是欧拉通路的起点和终点..并且该图连通
3. 我自己加一条，其实是对2的理解： 入读-出度>1 时直接return false ，排除 a->b a->c 这种情况
判断欧拉回路：
无向图是欧拉图的充要条件是所有点的度为偶数并且所有点联通
有向图是欧拉图的充要条件是所有点的入度=出度..并且联通...
判断连通
1. dfs遍历， 这里有一份参考代码 不过我一直怀疑其正确性。因为你无法确定有向图的起点，比如 a->b->c 如果你从b点开始搜的话就会悲催，但是你不知道b点上面还有没有点。
2. 并查集，并查集的方便之处不用废话。但是在图论中两点之间有多条边时需要注意一些细节的处理。
关于判断入读出度
一种办法是分别记录 in[] out[]
我用的办法是一个数组：sz[x]++ 表示拉出一条边，sz[x]--表示走来一条边，sz[x]==1 sz[x]==-1 就是上面的两种情况
上代码吧
这是只开sz[]的
#include <iostream>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#define N 101010
using namespace std;
int sz[333];
int fa[333];
bool ok[333]; // 数据中使用到的单词
int n, T;
int getfa(int v)
{
if ( fa[v] == v ) return v;
return fa[v] = getfa(fa[v]);
}
void init()
{
memset(ok, 0, sizeof(ok));
memset(sz, 0, sizeof(sz));
cin >> n;
string a;
for ( int i(‘a’); i <= ‘z’; i++) fa[i] = i;
for ( int i(1); i <= n; i++)
{
cin >> a;
int x = a[0], y = a[a.size() - 1];
fa[getfa(x)] = getfa(y);
ok[x] = ok[y] = true;
sz[x]++;
sz[y]–;
}
}
bool check()
{
int tf = 0 , i;
for ( i = ‘a’; i <= ‘z’; i++)
{
if (ok[i])
{
if ( !tf ) tf = getfa(i);
else if ( getfa(i) != tf ) return false; // 不连通
}
}
int c1 = 0, c2 = 0;
for ( int i('a'); i <= 'z'; i++)
{
if (!ok[i]) continue;
if ( sz[i] == 0 ) continue;
else if ( sz[i] == 1 ) c1++;
else if ( sz[i] == -1) c2++;
else return false; // 其它乱七八糟的情况 比如 ab ab out[a]=2 in[b]=2
}
if ( (c1 == 1 && c2 == 1) || (c1 == 0 && c2 == 0) ) // 单向路径 or 回路
return true;
else
return false;
}
int main()
{
freopen(“in.txt”, “r”, stdin);
for ( cin >> T; T–; )
{
init();
if (check())
cout << “Ordering is possible.” << endl;
else
cout << “The door cannot be opened.” << endl;
}
}
为保险起见，还是开了两个数组的
#include <iostream>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#define N 101010
using namespace std;
int in[333], out[333];
int fa[333];
bool ok[333]; // 数据中使用到的单词
int n, T;
int getfa(int v)
{
if ( fa[v] == v ) return v;
return fa[v] = getfa(fa[v]);
}
void init()
{
memset(ok, 0, sizeof(ok));
memset(in, 0, sizeof(in));
memset(out, 0, sizeof(out));
cin >> n;
string a;
for ( int i(‘a’); i <= ‘z’; i++) fa[i] = i;
for ( int i(1); i <= n; i++)
{
cin >> a;
int x = a[0], y = a[a.size() - 1];
fa[getfa(x)] = getfa(y);
ok[x] = ok[y] = true;
out[x]++;
in[y]++;
}
}
bool check()
{
int tf = 0 , i;
for ( i = ‘a’; i <= ‘z’; i++)
{
if (ok[i])
{
if ( !tf ) tf = getfa(i);
else if ( getfa(i) != tf ) return false; // 不连通
}
}
int c1 = 0, c2 = 0;
for ( int i('a'); i <= 'z'; i++)
{
if (!ok[i]) continue;
if ( in[i] == out[i] ) continue;
else if ( in[i] - out[i] == 1 ) c1++;
else if ( in[i] - out[i] == -1) c2++;
else return false;
//else {printf("%d%d\n",in[i],out[i]);return false;} // 其它乱七八糟的情况
}
if ( (c1 == 1 && c2 == 1) || (c1 == 0 && c2 == 0) ) // 单向路径 or 回路
return true;
else
return false;
}
int main()
{
//freopen(“in.txt”, “r”, stdin);
for ( cin >> T; T–; )
{
init();
if (check())
cout << “Ordering is possible.” << endl;
else
cout << “The door cannot be opened.” << endl;
}
}
