P1341 无序字母对 题解

· · 个人记录

欧拉回路典型例题，也称为一笔画问题。先讲一下欧拉图，半欧拉图，欧拉路径，欧拉回路的概念。

欧拉路径：每一条边恰好经过一次的路径。

欧拉回路：每一条边恰好经过一次的回路。

欧拉图：有欧拉回路的图。

半欧拉图：有欧拉路径，无欧拉回路的图。

一些性质：对于一个无向图来说，如果是欧拉图，当且仅当图中每个点度为偶数且连通。如果是半欧拉图，当且仅当图中有两个点度为奇数且连通。

此题显然是求一个图有无欧拉路径，并且输出字典序最小的一个答案。

那我们可以先判断是否有欧拉路径，因为有欧拉图一定有欧拉路径，可以理解为欧拉回路包含欧拉路径，所以如果这个图中度为奇数的点不为0（即不为欧拉图）且不为2（即不为半欧拉图），那么一定没有欧拉路径。或者这个图压根不连通。

由于题目给的是字符，考虑先把字符转成数字，需要输出的时候再把数字转化成原字符的ASCII码就行。用强制类型转化 (char) 输出。

dfs的时候x表示当前的点，建图时邻接矩阵，由于字典序最小，枚举到达的点时从1-55。如果有边，删去就行，从到达的点继续dfs。也是找欧拉路径的一个模板。


#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<stack>
using namespace std;
stack<int> s;
int edge[1010][1010],in[1010];
int u,v,n,cnt,id;
char ch[10];
int change1(char x)//字符转化为数字 
{
    if(x>='A'&&x<='Z') return x-'A'+1;//转化为数字，A为1；
    return x-'a'+27;// 由于有26个英文字母，所以a从27开始表示 
}
int change2(int x)//数字转化为字符的ASCII码 
{
    if(x>=1&&x<=26) return x+'A'-1;
    return x+'a'-27;
}
void dfs(int x)
{
    for(int i=1;i<=55;i++)
    {
        if(edge[x][i])
        {
            edge[x][i]--;
            edge[i][x]--;
            dfs(i);
        }
    }
    s.push(x);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>ch;
        u=change1(ch[0]);
        v=change1(ch[1]);
        in[u]++;
        in[v]++;
        edge[u][v]++;
        edge[v][u]++;
    }
    for(int i=1;i<=55;i++)
    {
        if(in[i]%2==1)
        {
            cnt++;
            if(!id)
            id=i;
        }
    }
    if(cnt!=0&&cnt!=2)
    {
        printf("No Solution\n");
        return 0;
    }
    if(cnt==0)//如果是欧拉图，那就从有度的字典序最小的开始走。
    {
        for(int i=1;i<=55;i++)
        {
            if(in[i])
            {
                id=i;
                break;
            }
        }
    }
    dfs(id);
    while(s.size())
    {
        cout<<(char)change2(s.top());
        s.pop();
    }
    return 0;
}