欧拉路径＆无序字符对

· · 题解

如果对于欧拉路径还有不太清晰的同学可以先阅此页：

欧拉回路及其相关

定义：

１.这个问题主要引伸自一个古老的问题，有兴趣的同学可以上百度百科上找。通俗而言，就是一个一笔划问题。

２.给定一个图，经过每条边一次且仅此一次的一条回路called欧拉回路。||给定一个图，经过每条边一次且仅此一次的路径callde欧拉路径。

３.欧拉图：存在欧拉回路的图。半欧拉图：存在欧拉路径，且不存在欧拉回路的图。 联系：

据某巨弱而言，欧拉回路属于欧拉路径，而欧拉路径要求远比欧拉回路要求低。

规律＆性质：

对 无向图 而言：

１.定理一：若图为欧拉图，当且仅当图中每个点度数为偶数且联通。

证明：对于每个点，既可以进也可以出，所以绝对是可以做到欧拉路径的。

由此，可以引申至对于欧拉回路的求解算法：若存在欧拉回路，则从任意一个点出发向任意与其相连的点递归搜索，都是可以遍历回到起点的。

不仅如此，还可以引申出一个证明半欧拉图的推论：

推论一：若图为半欧拉图，当且仅当图中有两点度数为奇数，其他点度数皆为偶数且联通。

对于 有向图 而言：

２.定理二：有向图为欧拉图，当且仅当它的基图联通，且所有点的入度等于出度即可。（注意区别）；

推论二：有向图为半欧拉图，当且仅当其中一个顶点的入度少于出度１，而另一点出度少于入度１，基图联通时。

知道了定理还需要了解一些性质才可以求解欧拉回路：

性质一：当c是图中一个简单回路，此回路删去，留下的图的各极大联通子图都存在一条欧拉回路。（显然，用点将各联通子图连接，才能形成欧拉回路。）

性质二：当Ｃ1Ｃ2是两个简单回路，无边相交，仅有一点公共，可以将其合并成另一个简单回路。

再贴上此题：

糖果

思路：

这道题是一道裸的欧拉路径的题目，对于此题，我们要将每一个字符化成一个点来看待，每次给出的关系都可以做为一条边来看待。

这样，我们不难发现，求某一个将所有关系满足的排列，就是在构造图中找到一条欧拉路径。

把它作为半欧拉图来看待，首先我们需要对它的存在性进行判断，如果出现了两个以上入度为一的点，那么毫无疑问此图不满足条件，输出"No Solution" 即可。

我们还要考虑几种情况，首先，可能不存在入度为一的点，那么构成欧拉图，也符合要求。其次，可能只有一个点入度为一，也是不符合的。这点需要特判。

对于此题的解决方法，容易让人想到的就是深搜，但还有许多细节需要注意：１.对于字母的处理，我们可以用到map存，一个存每个字母对应编号，另一个存每个编号对应字母，注意存图。（某龚姓大佬指点）； ２.搜索要注意回溯，尽量在每一个搜索树的层上保留每一步的数据； ３.此题情况较多要进行细致讨论（不要学我）； ４.满足题目要求，要按字典序处理（此时龚姓大佬又出场）先将边按字母序列排好，再建图（也可不建),遍历字母选择开端即可，预设字符串为空，每行一步加上即可。

贴上代码：

#include<bits/stdc++.h>
using namespace std;

const int N=1e+5;
int n, cnt, t, start, end, step;
int head[N], next[N], to[N], w[N];
int du[N];
string s;
bool vis[N];
struct node{
    int to,from,p;
}edge[N];
map<int,char>letter;
map<char,int>num;
bool cmp(const node&a,const node&b){
    return a.to > b.to;
}
void add(int u, int v, int p){
    next[++t] = head[u];
    to[t] = v;
    w[t] = p;
    head[u] = t;
    ++du[u];
}

void dfs(int x, int step, string s){
    if(!x) return ;
    s+=letter[x];
    if(step == n + 1){
        if(x == end||end == 0){
            cout << s;
            exit(0);
        }//细节。
        return ;
    }
    for(int i = head[x]; i; i = next[i]){
        if(!vis[w[i]]&&!vis[w[i]^1]){
            vis[w[i]] = 1;
            dfs(to[i], ++step, s);//也可以写成step+1;可以减少回溯。
            vis[w[i]]=0;
            step--;//注意回溯。
        }
    }
}           

int main(){
    //freopen("unorder.in", "r", stdin);
    //freopen("unorder.out", "w", stdout);
    scanf("%d", &n);
    char a, b;
    for(int i = 0; i <= 25; i++){
        num[i +'A'] = i + 1, letter[i + 1] = i +'A';
        num[i +'a'] = i + 27,letter[i + 27] = i +'a';
    }//注意此处龚式处理。
    for(int i = 1; i <= n; i++){
        cin >> a >> b;
        edge[++cnt] = (node){num[a], num[b], i<<1};
        edge[++cnt] = (node){num[b], num[a], i<<1|1};//打上标记，可以有益于之后的判断，是不是很巧妙啊，可惜不是我想的。
    }
    sort(edge + 1, edge + cnt + 1, cmp);
    for(int i =1; i <= cnt; i++){
        add(edge[i].from, edge[i].to, edge[i].p);
    }
    for(int i = 1;i <= 52; i++){
        if(du[i] & 1){
            if(!start) start=i;
            else if(!end) end=i;
            else{
                printf("No Solution");
                return 0;
            }
        }
    }//特判，若没有，则随机找第一个入度为二即可。
    if(!start){
        for(int i = 1; i <= 52; i++){
            if(du[i]){
                start=i;
                break;
            }
        }
    }
    s="";
    dfs(start, step+1, s);
    printf("No Solution");
    return 0;
}