欧拉

欧拉序是由瑞士数学家莱昂哈德·欧拉（Leonhard Euler）首次提出的概念，他在1736年发表了一篇关于图论的论文，其中提到了欧拉序的概念。但需要注意的是，“欧拉序”并不是一个广泛接受的专业术语，更常见的说法是“欧拉迹”或“欧拉路径”、“欧拉回路”。

欧拉路径（Euler path）、欧拉回路（Euler circuit）是图论中的重要概念，指的是在无向图或弱连通的有向图中，经过每条边且只经过一次的路径。如果这条路径是闭合的，即起点和终点是同一点，那么称为欧拉回路。

欧拉序

例题 #1 金字塔

题目描述

一棵树，每个节点上有颜色，给出颜色的欧拉序，求可能的树的数量。

因为结果可能会非常大，你只需要输出答案对\(10^9\) 取模之后的值。

入格式

输入仅一行，包含一个字符串 \(S\)，长度不超过 \(300\)，表示机器人得到的颜色序列。

输出格式

输出一个整数表示答案。

---

www.luogu.com.cn

/*                                                                                
                      Keyblinds Guide
                    ###################
      @Ntsc 2024

      - Ctrl+Alt+G then P : Enter luogu problem details
      - Ctrl+Alt+B : Run all cases in CPH
      - ctrl+D : choose this and dump to the next
      - ctrl+Shift+L : choose all like this
      - ctrl+K then ctrl+W: close all
      - Alt+la/ra : move mouse to pre/nxt pos'

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

#define rep(i, l, r) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(i, r, l) for (int i = r, END##i = l; i >= END##i; --i)
#define pb push_back
#define mp make_pair
#define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define ps second
#define pf first

// #define innt int
#define itn int
// #define inr intw
// #define mian main
// #define iont int

#define rd read()
int read(){
    int xx = 0, ff = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            ff = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
      xx = xx * 10 + (ch - '0'), ch = getchar();
    return xx * ff;
}
void write(int out) {
    if (out < 0)
        putchar('-'), out = -out;
    if (out > 9)
        write(out / 10);
    putchar(out % 10 + '0');
}

#define ell dbg('\n')
const char el='\n';
const bool enable_dbg = 1;
template <typename T,typename... Args>
void dbg(T s,Args... args) {
    if constexpr (enable_dbg){
    cerr << s;
    if(1)cerr<<' ';
        if constexpr (sizeof...(Args))
            dbg(args...);
    }
}

#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif


const int N = 3e2 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 1e9 + 0;



string s;

itn f[N][N];

void solve(){
    cin>>s;
    int n=s.size();
    s=" "+s;

    for(int i=1;i<=n;i++){
        f[i][i]=1;
    }

    for(int l=2;l<=n;l++){
        for(int i=1;i+l-1<=n;i++){
            int j=i+l-1;
            if(s[i]!=s[j])continue;
            for(int k=i+2;k<=j;k++){
                if(s[i]==s[k])f[i][j]+=f[i+1][k-1]*f[k][j]%MOD;
                f[i][j]%=MOD;
            }
        }
    }

    cout<<f[1][n]<<endl;
}

signed main(){
    int T=1;
    while(T--){
        solve();
    }
    return 0;
}

欧拉路径

求有向图字典序最小的欧拉路径。欧拉回路是欧拉路径的一种。

一句话来说，就是先判定有无解，若有解，找到起点后能走即走，走过删边即可！

欧拉路径（欧拉通路）：通过图中所有边的简单路。（换句话说，每条边都通过且仅通过一次）也叫”一笔画”问题。

有向图欧拉路径：

图中**恰好**存在 1 个点出度比入度多 1（这个点即为 起点 S），1 个点入度比出度多 1（这个点即为 终点 T），其余节点出度=入度。或者**图为一个环**，即所有点的入度=出度。

寻找欧拉路径（默认存在）：

• 首先根据题意以及判定先确定起点 S。

• 从起点 S 开始 dfs 。

dfs(x) 中我们从小到大（按出边指向的点的编号大小排序）枚举。枚举到一个还没有访问的边就标记为已经访问，然后 dfs 下去。 同时记录经过的点的编号。

注意我们要用**栈**来记录答案而不是数组！

我们也可以进行优化，记录\(del_x\)为点\(x\)的出边已经访问过了\(del_x-1\)条，下次应该从第\(del_x\)条开始访问。

/*////////ACACACACACACAC///////////
       . Code  by  Ntsc .
       . Earn knowledge .
/*////////ACACACACACACAC///////////

#include<bits/stdc++.h>
#define int long long
#define db double
#define rtn return
using namespace std;

const int N=2e5+5;
const int M=1e5;
const int Mod=1e5;
const int INF=1e5;

int n,m,p,q,T,ans[N];
vector<int> e[N],vis[N];
int ind[N],oud[N],del[N];
int s,t,cnt;


stack<int> st;

void add(int a,int b){
    e[a].push_back(b);
    ind[b]++;oud[a]++;
}

bool check(){
    s=1;
    int flg=1,cnta=0,cntb=0;
    for(int i=1;i<=n;i++){
        if(ind[i]==oud[i])continue;
        flg=0;
        if(ind[i]==oud[i]-1){
            s=i;cnta++;
        }else if(ind[i]==oud[i]+1){
            t=i;cntb++;
        }else return 0;
    }

    return (cnta==cntb&&cnta==1)||flg;
}

void dfs(int x){
//  ans[++cnt]=x;
    for(int i=del[x];i<e[x].size();i=del[x]){
        del[x]=i+1;
        dfs(e[x][i]);
    }
    st.push(x);
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);
    }

    for(int i=1;i<=n;i++){
        sort(e[i].begin(),e[i].end());
    }
    if(!check()){
        cout<<"No"<<endl;
        return 0;
    }

    dfs(s);
    while(st.size())cout<<st.top()<<' ',st.pop();

    return 0;
}

例题 #1 无序字母对

题目描述

给定 \(n\) 个各不相同的无序字母对（区分大小写，无序即字母对中的两个字母可以位置颠倒）。请构造一个有 \((n+1)\) 个字母的字符串使得每个字母对都在这个字符串中出现。

输入格式

第一行输入一个正整数 \(n\)。

第二行到第 \((n+1)\) 行每行两个字母，表示这两个字母需要相邻。

输出格式

输出满足要求的字符串。

如果没有满足要求的字符串，请输出 No Solution。

如果有多种方案，请输出字典序最小的方案（即满足前面的字母的 ASCII 编码尽可能小）。

不同的无序字母对个数有限，\(n\) 的规模可以通过计算得到。

---

我们只需要将字符对建成无向边，那么这道题就是要我们求字典序最小的欧拉路径了。

注意这里是无向图欧拉路径，走了一条边要把他和他的反边一起删掉。

/*                                                                                
                      Keyblinds Guide
                    ###################
      @Ntsc 2024

      - Ctrl+Alt+G then P : Enter luogu problem details
      - Ctrl+Alt+B : Run all cases in CPH
      - ctrl+D : choose this and dump to the next
      - ctrl+Shift+L : choose all like this
      - ctrl+K then ctrl+W: close all
      - Alt+la/ra : move mouse to pre/nxt pos'

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

#define rep(i, l, r) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(i, r, l) for (int i = r, END##i = l; i >= END##i; --i)
#define pb push_back
#define mp make_pair
#define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define ps second
#define pf first

// #define innt int
#define itn int
// #define inr intw
// #define mian main
// #define iont int

#define rd read()
int read(){
    int xx = 0, ff = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            ff = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
      xx = xx * 10 + (ch - '0'), ch = getchar();
    return xx * ff;
}
void write(int out) {
    if (out < 0)
        putchar('-'), out = -out;
    if (out > 9)
        write(out / 10);
    putchar(out % 10 + '0');
}

#define ell dbg('\n')
const char el='\n';
const bool enable_dbg = 1;
template <typename T,typename... Args>
void dbg(T s,Args... args) {
    if constexpr (enable_dbg){
    cerr << s;
    if(1)cerr<<' ';
        if constexpr (sizeof...(Args))
            dbg(args...);
    }
}

#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif


const int N = 5e2 + 5;
const int INF = 1e3;
const int M = 200000;
const int MOD = 1e9 + 7;



int ans[M];
int top;
map<char,int > id;
int d[N][N];
int deg[N];


void add(int a,int b){
    d[a][b]=d[b][a]=1;
    deg[a]++;
    deg[b]++;
}

void dfs(int x){
    for(int i=1;i<=66;i++){
        if(d[x][i]>0){
            d[x][i]--,d[i][x]--;
            dfs(i);
        }
    }
    ans[++top]=x;
}

inline char change(int x){
    if(x<27)return (char)x-1+'A';
    return (char)x-27+'a';
}

void solve(){
    int n=rd;


    for(char i='a';i<='z';i++){
        id[i]=i-'a'+27;
    }

    for(int i='A';i<='Z';i++){
        id[i]=i-'A'+1;
    }
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        add(id[s[0]],id[s[1]]);
    }


    int cnt=0;
    int h=0;

    for(int i=1;i<=66;i++){
        if(deg[i]&1){//贪心先选小的
            cnt++;
            if(!h)h=i;
        }
    }


    if(cnt==1||cnt>2){
        puts("No Solution");
        exit(0);
    }


    if(!h){
        for(int i=1;i<=66;i++){
            if(deg[i]){
                h=i;
                break;
            }
        }
    }
    dfs(h);
    for(int i=top;i;i--){
        cout<<change(ans[i]);
    }
}

signed main() {
//     freopen("P2619_3.in","r",stdin);
    // freopen("center.out","w",stdout);

    int T=1;
    while(T--){
        solve();
    }
    return 0;
}

为什么上面优先选度数为奇数的，如果没有再选存在度数的呢？不是要最小化字典序吗？

→因为如果存在度数为奇数的，那么就可能存在无解的情况，并且此时只能选奇数的为开始才可以得到合法的欧拉路径。

没有奇数点存在，那么就是欧拉回路了，不存在欧拉路径，因此找一个最优的点作为起点。

欧拉回路

欧拉回路是图论中的一个基本概念，指的是在一个图中，经**过每一条边且仅经过一次，并最终回到起点的闭合路径**。

一个图存在欧拉回路的充分必要条件是图中所有的顶点具有偶数度，即与每个顶点相连的边的数目是偶数。具有欧拉回路的图被称为欧拉图。

具体来说，以下几个性质是等价的：

1. 图G有欧拉回路。

2. 图G是连通的，并且有零个或两个度数为奇数的顶点。

3. 图G是连通的，并且所有顶点的度数都是偶数。

例题 #1 [USACO3.3] 骑马修栅栏 Riding the Fences

John 是一个与其他农民一样懒的人。他讨厌骑马，因此从来不两次经过一个栅栏。

John 的农场上一共有 \(m\) 个栅栏，每一个栅栏连接两个顶点，顶点用 \(1\) 到 \(500\) 标号（虽然有的农场并没有那么多个顶点）。一个顶点上至少连接 \(1\) 个栅栏，没有上限。两顶点间可能有多个栅栏。所有栅栏都是连通的（也就是你可以从任意一个栅栏到达另外的所有栅栏）。John 能从任何一个顶点（即两个栅栏的交点）开始骑马，在任意一个顶点结束。

你需要求出输出骑马的路径（用路上依次经过的顶点号码表示)，使每个栅栏都恰好被经过一次。如果存在多组可行的解，按照如下方式进行输出：如果把输出的路径看成是一个 \(500\) 进制的数，那么当存在多组解的情况下，输出 \(500\) 进制表示法中最小的一个 （也就是输出第一位较小的，如果还有多组解，输出第二位较小的，以此类推）。

输入数据保证至少有一个解。

对于 \(100\%\) 的数据，\(1 \leq m \leq 1024,1 \leq u,v \leq 500\)。

题目翻译来自NOCOW。

USACO Training Section 3.3

---

其实和上面的例题是一样的。

/*                                                                                
                      Keyblinds Guide
                    ###################
      @Ntsc 2024

      - Ctrl+Alt+G then P : Enter luogu problem details
      - Ctrl+Alt+B : Run all cases in CPH
      - ctrl+D : choose this and dump to the next
      - ctrl+Shift+L : choose all like this
      - ctrl+K then ctrl+W: close all
      - Alt+la/ra : move mouse to pre/nxt pos'

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

#define rep(i, l, r) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(i, r, l) for (int i = r, END##i = l; i >= END##i; --i)
#define pb push_back
#define mp make_pair
#define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define ps second
#define pf first

// #define innt int
#define itn int
// #define inr intw
// #define mian main
// #define iont int

#define rd read()
int read(){
    int xx = 0, ff = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            ff = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
      xx = xx * 10 + (ch - '0'), ch = getchar();
    return xx * ff;
}
void write(int out) {
    if (out < 0)
        putchar('-'), out = -out;
    if (out > 9)
        write(out / 10);
    putchar(out % 10 + '0');
}

#define ell dbg('\n')
const char el='\n';
const bool enable_dbg = 1;
template <typename T,typename... Args>
void dbg(T s,Args... args) {
    if constexpr (enable_dbg){
    cerr << s;
    if(1)cerr<<' ';
        if constexpr (sizeof...(Args))
            dbg(args...);
    }
}

#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif


const int N = 500 + 5;
const int INF = 1e9;
const int M = 200;
const int MOD = 1e9 + 7;
 const double eps=1e-4;

int deg[N],ans[N];
int top;
int d[N][N];

 void add(int a,int b){
    d[a][b]++;
    d[b][a]++;
    deg[a]++;
    deg[b]++;
 }


 void dfs(int x){
    //随便走
    for(int i=1;i<=500;i++){
        if(d[x][i]>0){
            d[x][i]--;
            d[i][x]--;
            dfs(i);
        }
    }
    ans[++top]=x;
 }
void solve(){
    int m=rd;
    for(int i=1;i<=m;i++){
        int a=rd,b=rd;
        add(a,b);
    }

    int h=0;

    for(int i=1;i<=500;i++){
        if(deg[i]&1){
            h=i;
            break;
        }
    }

  //保证合法，所以不用判断了。

    if(!h){
        for(int i=1;i<=500;i++){
            if(deg[i]){
                h=i;
                break;
            }
        }
    }

    dfs(h);


    while(top)cout<<ans[top--]<<endl;


}
signed main() {
//     freopen("P2619_3.in","r",stdin);
    // freopen("center.out","w",stdout);

    int T=1;
    while(T--){
        solve();
    }
    return 0;
}