在纯无向图中
直接考虑每个点的度数（旁边所连的边的条数），在图连通的情况下只有两种情况存在“一笔画”
- 所有点的度数都为偶数，此时以任意点为起点，必然存在“欧拉回路”，且会回到该点
- 有且只有两点的度数为奇数，其他点度数都为偶数。此时从任意奇数点出发必然存在“欧拉道路”，且终点为另一奇数点 （以上结论请自行证明，提示：从点的入度出度成对入手）
在纯有向图中
考虑每个点的出度与入度，同样在图连通的情况下，只有两种情况存在“一笔画”
- 所有点的入度与出度都相等，此时以任意点为起点，必然存在“欧拉回路”，且会回到该点
- 有且只有两点入度与出度不相等，其他点入度与出度相等，并且入度与出度不相等的两点必然一点出度比入度大1，另一点出度比入度小1。此时以出度大1的点为起点，必然有存在一条“欧拉道路”，使得终点为另一点。
（以上结论同样请自行证明）
在混合图中（既有有向又有无向，同样每条边只能走一次）
也许你需要这个（点击） 直接上代码，~ ~ ```cpp #include
#include #include using namespace std; int zimu[55], pre[55]; int du[55]; int G[55][55];//两点间边的数量 int vis[55][55];//边走过的次数 stack q;
//字符与数字的相互转换 int chang (char c) { if ( c >= ‘a’ && c <= ‘z’) return c - ‘a’ + 27; return c - ‘A’ + 1; } char pt (int x) { if (x <= 26) return ‘A’ + x - 1; return ‘a’ + x - 27 ; }
//并查集 —判断连通性 int findd (int x) { int r=x;
while (pre[r] != r)
r = pre [r];
int i = x, j;
while (i != r)
{
j = pre [i];
pre[i] = r;
i = j;
}
return r; } void joinn (int a, int b) {
int x = findd(a), y = findd(b);
if ( x != y )
pre[x] = y; } bool pd_tonglu ( ) {
int x ;
bool pd = 1;
for (int i = 1; i <= 52; i++)
{
if ( findd(i) != i)
{
// cout<<i<<" "<<pt(findd(i))<<endl;
if (pd)
{
x = findd(i);
pd = 0;
}
else
if (x != findd(i))
return false;
}
}
return true; }
//建点 （顺带完成并查集的初始化）
void addnode (char a, char b)
{
du[a]++;
du[b]++;
G[a][b]++;
G[b][a]++;//存在两点之间多边的情况，这时应该考虑所有边
/*若使用 G[a][b] = G[b][a] = 1 ;
无法考虑多变的情况 例如 对于数据
4
ab
ba
ab
bc
可以手算检测得到 ababc （或是 cbaba）
但对于题解中的大部分程序 输出为 abc （或是没有输出）
对于输出为abc的程序 不满足题目要求 “构造一个有n+1个字母的字符串 ”
*/
joinn(a,b);
}
//开始查找 void euler (int u) { for (int v = 1; v <= 52; v++) { if (G[u][v] > vis [u][v]) { vis[u][v]++; vis[v][u]++;//无向 euler(v); // cout«pt(v)«”-“«pt(u)«” “; q.push(pt(u)); } } } int main() { //初始化 for (int i = 1; i <= 54; i++ )//并查集 初始化 pre[i] = i;
//输入
int n;
cin >> n;
for (int i = 1; i <= n; i++ )
{
char a, b;
cin >> a >> b;
addnode ( chang(a), chang(b));//通过 chang 来将字符转为点
// cout << chang(a) <<" "<< chang(b)<<endl;
}
//判断欧拉路径的存在性
if ( !pd_tonglu() ) //判断是否有通路
{
cout << "No Solution" << endl;
return 0;
}
int x1 = 100, x2, pd = 0;//pd要存三个值 代表奇点个数
for ( int i = 1; i <= 52; i++ )
{
if(du[i] && !pd)
x1 = min(i,x1);
if ( du[i] & 1 )
{
if ( !pd )
{
x1 = i ;
}
else
x2 = i;
pd++;
}
}
if ( pd != 2 && pd != 0) //没有奇点 或者 有且只有两个奇点时可以 （并且还要联通）
{
cout << "No Solution" << endl;
return 0;
}
euler(x1); //开始搜索寻找欧拉回路
char st = q.top();
while ( !q.empty() )
{
cout << q.top() ;
q.pop();
}
if ( pd == 2 )
cout << pt(x2) << endl;
else
cout << st << endl;
return 0; } ```
