Poj 1386欧拉回路
题意：如果单词A的结尾字母与单词B的首字母相同，那么可以认为是A到B相通。给出一系列单词，求这些词按照某种排列能否串通。
题解：
如果直接按照题意建模，以单词为顶点，边表示两两相通，那么将会得到哈密顿回路模型。显然是很难解的。
换一种方式，以字母为顶点，边表示传送的单词，那么就得到欧拉回路模型的图，可以按照欧拉定理求解。
以下给出Euler图的相关知识：
Euler回路：G中经过每条边一次且仅一次的回路
Euler路径：G中经过每条边一次且仅一次的路径
无向图存在Euler回路定理：当它是连通图+顶点度数为偶数
无向图存在Euler路径定理：当它是连通图+除两个顶点度为奇数外，其余为偶数
有向图存在Euler回路定理：当它是连通图+顶点入度 == 出度
有向图存在Euler路径定理：当它是连通图+除一个顶点的入度和出度的差的绝对值小1外，其余相等
代码： #include <stdio.h>
#include <string.h>
const int N = 30;class UnionSet
{
private:
int parent[N];
int rank[N];
int size;
public:
UnionSet(int _size):size(_size)
{
init();
}
~UnionSet()
{
}void init()
{
for(int i = 0; i < size; ++i)
{
parent[i] = -1;
rank[i] = 1;
}
}int root(int _x)
{
int r = _x;
while(parent[r] >= 0)
r = parent[r];
int i = _x;
int j;
while(parent[i] >= 0)
{
j = parent[i];
parent[i] = r;
i = j;
}
return r;
}int Union(int _r1,int _r2)
{
if(_r1 == _r2)
return _r1;
else
{
int root1 = root(_r1);
int root2 = root(_r2);
if(root1 == root2)
return root1;
if(rank[root1] > rank[root2])
{
parent[root2] = root1;
rank[root1] += rank[root2];
}
else
{
parent[root1] = root2;
rank[root2] += rank[root1];
}
}
}
int getRank(int _x)
{
return rank[_x];
}
};
char buf1[1024];void Test()
{
int In[30] = {0};
int Out[30] = {0};
bool visited[30] = {false};
UnionSet Set(28);
int n;
scanf("%d",&n);
bool flag = false;
int start = 0;
for (int i = 0; i < n; ++i)
{
scanf("%s",buf1);
int len = strlen(buf1);
Set.Union(buf1[0] - a,buf1[len-1] - a);
In[buf1[len-1] - a]++;
Out[buf1[0] - a]++;
visited[buf1[0] - a] = true;
visited[buf1[len-1] - a] = true;
if (!flag)
{
start = buf1[0] - a;
flag = true;
}
}
for (int i = 0; i < 26; ++i)
{
if (i != start)
{
if (visited[i] && (Set.root(start) != Set.root(i)))
{
printf("The door cannot be opened. ");
return;
}
}
}
int cntIn = 0;
int cntOut = 0;
for (int i = 0; i < 26; ++i)
{
if (visited[i])
{
if (In[i] != Out[i])
{
if (In[i] - Out[i] == -1)
{
cntIn++;
}
else if (In[i] - Out[i] == 1)
{
cntOut++;
}
else
&nbs
补充：软件开发 , C语言 ,
