基础前置知识：

有向图：

欧拉路径：

定义：在有向图中，从一个顶点出发，经过每条边恰好一次，并且遍历所有顶点的路径称为有向图的欧拉路径。

特征：有向图存在欧拉路径，当且仅当该图是连通的，且除了两个顶点外，其余顶点的入度等于出度。这两个特殊顶点中，一个顶点的入度比出度大 1（终点），另一个顶点的出度比入度大 1（起点）。如果全部点的入度和出度数都是相等的也可以。

欧拉回路：

定义：在有向图中，从一个顶点出发，经过每条边恰好一次，最后回到起始顶点的路径称为有向图的欧拉回路。

特征：有向图存在欧拉回路，当且仅当该图是连通的，且所有顶点的入度等于出度。

无向图

欧拉路径：

定义：在无向图中，从一个顶点出发，经过每条边恰好一次，并且遍历所有顶点的路径称为无向图的欧拉路径。

特征：无向图存在欧拉路径，当且仅当该图是连通的，且图中奇度顶点（度数为奇数的顶点）的个数为 0 或 2。若奇度顶点个数为 0，则可以从任意顶点出发；若奇度顶点个数为 2，则必须从其中一个奇度顶点出发，到另一个奇度顶点结束。

欧拉回路：

定义：在无向图中，从一个顶点出发，经过每条边恰好一次，最后回到起始顶点的路径称为无向图的欧拉回路。

特征：无向图存在欧拉回路，当且仅当该图是连通的，且所有顶点的度数均为偶数。

4个板子题

有向图的欧拉路径：

题目描述

求有向图字典序最小的欧拉路径。

输入格式

第一行两个整数 n,m 表示有向图的点数和边数。

接下来 m 行每行两个整数 u,v 表示存在一条 u→v 的有向边。

输出格式

如果不存在欧拉路径，输出一行 No。

否则输出一行 m+1 个数字，表示字典序最小的欧拉路径。

代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 100005;

// 存储图的邻接表

vector<int> g[N];

// 记录每个节点的入度

int in[N];

// 记录每个节点的出度

int out[N];

// 存储欧拉路径

int s[N];

int top=0;

// 深度优先搜索函数，用于寻找欧拉路径

void dfs(int u) {

    // 遍历从节点 u 出发的所有边

    while (!g[u].empty()) {

        // 取出字典序最小的邻接节点

        int v = g[u].back();

        g[u].pop_back();

        // 递归调用 dfs 函数继续搜索

        dfs(v);

    }

    // 将节点 u 加入欧拉路径

    s[++top]=u;

}

int main() {

    int n, m;

    // 读取图的点数 n 和边数 m

    cin >> n >> m;

    // 读取每条边的信息，并更新入度和出度

    for (int i = 0; i < m; i++) {

        int u, v;

        cin >> u >> v;

        // 将边 (u, v) 加入邻接表

        g[u].push_back(v);

        // 节点 v 的入度加 1

        in[v]++;

        // 节点 u 的出度加 1

        out[u]++;

    }

    // 对每个节点的邻接表进行排序，以保证按字典序遍历

    for (int i = 1; i <= n; i++) {

        sort(g[i].begin(), g[i].end(), greater<int>());

    }

    

    // 寻找可能的起始节点

    int start = 1;

    int cnt = 0;

    bool flag = true;

    for (int i = 1; i <= n; i++) {

        if (out[i] - in[i] == 1) {

            // 出度比入度大 1 的节点作为起始节点

            start = i;

            cnt++;

        } else if (out[i] - in[i] == -1) {

            cnt++;

        } else if (out[i] != in[i]) {

            // 若存在节点入度和出度差值不为 0、1 或 -1，则不存在欧拉路径

            flag = false;

            break;

        }

    }

    // 欧拉路径要求要么所有节点入度等于出度（欧拉回路），要么有两个节点入度和出度差值为 1 和 -1

    if (cnt != 0 && cnt != 2) {

        flag = false;

    }

    if (!flag) {

        // 若不存在欧拉路径，输出 No

        cout << "No" << endl;

    } else {

        // 从起始节点开始深度优先搜索

        dfs(start);

        // 输出欧拉路径

        while (top) {

            cout << s[top--];

            if (top) {

                cout << " ";

            }

        }

        cout << endl;

    }

    return 0;

}

无向图的欧拉路径：

重点是度数的奇偶性

同样的上面的题，但是改成无向图

题目描述

求无向图字典序最小的欧拉路径。

输入格式

第一行两个整数 n,m 表示有向图的点数和边数。

接下来 m 行每行两个整数 u,v 表示存在一条 u→v 的有向边。

输出格式

如果不存在欧拉路径，输出一行 No。

否则输出一行 m+1 个数字，表示字典序最小的欧拉路径。

代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 100005;

// 存储图的邻接表

vector<int> g[N];

// 记录每个节点的度数

int degree[N];

// 存储欧拉路径

int s[N];int top = 0;

// 深度优先搜索函数，用于寻找欧拉路径

void dfs(int u) {

    // 遍历从节点 u 出发的所有边

    while (!g[u].empty()) {

        // 取出字典序最小的邻接节点

        int v = g[u].back();

        // 从 u 的邻接表中删除 v，同时也从 v 的邻接表中删除 u（无向图）

        g[u].pop_back();

        it = find(g[v].begin(), g[v].end(), u);

        if (it != g[v].end()) {

            g[v].erase(it);

        }

        // 递归调用 dfs 函数继续搜索

        dfs(v);

    }

    // 将节点 u 加入欧拉路径

s[++top] = u;

}

int main() {

    int n, m;

    // 读取图的点数 n 和边数 m

    cin >> n >> m;

    // 读取每条边的信息，并更新节点度数

    for (int i = 0; i < m; i++) {

        int u, v;

        cin >> u >> v;

        // 将边 (u, v) 加入邻接表（无向图，双向添加）

        g[u].push_back(v);

        g[v].push_back(u);

        // 节点 u 和 v 的度数都加 1

        degree[u]++;

        degree[v]++;

    }

    // 对每个节点的邻接表进行排序，以保证按字典序遍历

    for (int i = 1; i <= n; i++) {

        sort(g[i].begin(), g[i].end(), greater<int>());

    }

    // 寻找可能的起始节点

    int start = 1;

    int oddDegreeCount = 0;

    bool flag = true;

    for (int i = 1; i <= n; i++) {

        if (degree[i] % 2 == 1) {

            // 度数为奇数的节点

            oddDegreeCount++;

            start = i;

        }

        if (degree[i] % 2 == 1 && oddDegreeCount > 2) {

            // 若奇数度数节点超过 2 个，则不存在欧拉路径

            flag = false;

            break;

        }

    }

    if (oddDegreeCount != 0 && oddDegreeCount != 2) {

        // 奇数度数节点不为 0 或 2 时，不存在欧拉路径

        flag = false;

    }

    if (!flag) {

        // 若不存在欧拉路径，输出 No

        cout << "No" << endl;

    } else {

        // 从起始节点开始深度优先搜索

        dfs(start);

        // 输出欧拉路径

        while (top) {

            cout << s[top--];

            if (top) {

                cout << " ";

            }

        }

        cout << endl;

    }

return 0;

}

有向图的欧拉回路：

题目描述

求有向图字典序最小的欧拉回路。

输入格式

第一行两个整数 n,m 表示有向图的点数和边数。

接下来 m 行每行两个整数 u,v 表示存在一条 u→v 的有向边。

输出格式

如果不存在欧拉路径，输出一行 No。

否则输出一行 m+1 个数字，表示字典序最小的欧拉路径。

代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 100005;

// 存储图的邻接表

vector<int> g[N];

// 记录每个节点的入度

int in[N];

// 记录每个节点的出度

int out[N];

// 存储欧拉回路

int s[N];int top = 0;

// 深度优先搜索函数，用于寻找欧拉回路

void dfs(int u) {

    // 遍历从节点 u 出发的所有边

    while (!g[u].empty()) {

        // 取出字典序最小的邻接节点

        int v = g[u].back();

        g[u].pop_back();

        // 递归调用 dfs 函数继续搜索

        dfs(v);

    }

    // 将节点 u 加入欧拉回路

    s[++top] = u;}

int main() {

    int n, m;

    // 读取图的点数 n 和边数 m

    cin >> n >> m;

    // 读取每条边的信息，并更新入度和出度

    for (int i = 0; i < m; i++) {

        int u, v;

        cin >> u >> v;

        // 将边 (u, v) 加入邻接表

        g[u].push_back(v);

        // 节点 v 的入度加 1

        in[v]++;

        // 节点 u 的出度加 1

        out[u]++;

    }

    // 对每个节点的邻接表进行排序，以保证按字典序遍历

    for (int i = 1; i <= n; i++) {

        sort(g[i].begin(), g[i].end(), greater<int>());

    }

    // 检查是否存在欧拉回路  和上面唯一不一样的地方

    bool flag = true;

    for (int i = 1; i <= n; i++) {

        if (in[i] != out[i]) {

            // 若存在节点入度和出度不相等，则不存在欧拉回路

            flag = false;

            break;

        }

    }

    if (!flag) {

        // 若不存在欧拉回路，输出 No

        cout << "No" << endl;

    } else {

        // 从节点 1 开始深度优先搜索

        dfs(1);

        // 输出欧拉回路

        while (top) {

            cout << s[top--];

            if (top) {

                cout << " ";

            }

        }

        cout << endl;

    }

return 0;

}

无向图的欧拉回路

题目描述

求无向图字典序最小的欧拉回路。

输入格式

第一行两个整数 n,m 表示有向图的点数和边数。

接下来 m 行每行两个整数 u,v 表示存在一条 u→v 的有向边。

输出格式

如果不存在欧拉路径，输出一行 No。

否则输出一行 m+1 个数字，表示字典序最小的欧拉路径。

代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 100005;

// 存储图的邻接表

vector<int> g[N];// 记录每个节点的度数int degree[N];// 存储欧拉回路int s[N];int top = 0;

// 深度优先搜索函数，用于寻找欧拉回路void dfs(int u) {

    // 遍历从节点 u 出发的所有边

    while (!g[u].empty()) {

        // 取出字典序最小的邻接节点

        int v = g[u].back();

        // 从 u 的邻接表中删除 v，同时也从 v 的邻接表中删除 u（无向图）

        g[u].pop_back();

        auto it = find(g[v].begin(), g[v].end(), u);

        if (it != g[v].end()) {

            g[v].erase(it);

        }

        // 递归调用 dfs 函数继续搜索

        dfs(v);

    }

    // 将节点 u 加入欧拉回路

    s[++top] = u;}

int main() {

    int n, m;

    // 读取图的点数 n 和边数 m

    cin >> n >> m;

    // 读取每条边的信息，并更新节点度数

    for (int i = 0; i < m; i++) {

        int u, v;

        cin >> u >> v;

        // 将边 (u, v) 加入邻接表（无向图，双向添加）

        g[u].push_back(v);

        g[v].push_back(u);

        // 节点 u 和 v 的度数都加 1

        degree[u]++;

        degree[v]++;

    }

    // 对每个节点的邻接表进行排序，以保证按字典序遍历

    for (int i = 1; i <= n; i++) {

        sort(g[i].begin(), g[i].end(), greater<int>());

    }

    // 检查是否存在欧拉回路  改变的地方

    bool flag = true;

    for (int i = 1; i <= n; i++) {

        if (degree[i] % 2 != 0) {

            // 若存在节点度数为奇数，则不存在欧拉回路

            flag = false;

            break;

        }

    }

    if (!flag) {

        // 若不存在欧拉回路，输出 No

        cout << "No" << endl;

    } else {

        // 从节点 1 开始深度优先搜索

        dfs(1);

        // 输出欧拉回路

        while (top) {

            cout << s[top--];

            if (top) {

                cout << " ";

            }

        }

        cout << endl;

    }

return 0;

}

练习题：

USACO3.3 骑马修栅栏 

题目背景

Farmer John 每年有很多栅栏要修理。他总是骑着马穿过每一个栅栏并修复它破损的地方。

题目描述

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

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

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

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

输入格式

第一行一个整数 m，表示栅栏的数目。

从第二行到第 (m+1) 行，每行两个整数 u,v，表示有一条栅栏连接 u,v 两个点。

输出格式

共 (m+1) 行，每行一个整数，依次表示路径经过的顶点号。注意数据可能有多组解，但是只有上面题目要求的那一组解是认为正确的。

数据保证至少有一组可行解。

代码

#include <bits/stdc++.h>

using namespace std;

const int N=2000;//说好的1-500，开到了2000才过最后一个

vector<int> g[N];

int s[N];

int top=0;

int degree[N]={0};

int m;

//逆序最小==>在dfs的循环中，大的先想办法让他们后遍历，后入栈

//dfs在回溯后，当前点u才入栈，所以尽可能让小的点当做start

//欧拉路径 ==> 0/2个奇数点

bool cmp(int u,int v){

    return u>v;

}

void dfs(int u){

    while(!g[u].empty()){

        int v=g[u].back();

        g[u].pop_back();

        auto it=find(g[v].begin(),g[v].end(),u);

        if(it!=g[v].end()){

            g[v].erase(it);

        }

        dfs(v);

    }

    s[++top]=u;

}

int main(){

    scanf("%d",&m);

    int n=0;

    int minn=0x3f3f3f3f;

    for(int i=0;i<m;i++){

        int u,v;

        scanf("%d%d",&u,&v);

        n=max(n,max(u,v));

        minn=min(minn,min(u,v));

        g[u].push_back(v);

        g[v].push_back(u);

        degree[u]++;degree[v]++;

    }

    int start=minn;

    while(!degree[start])start++;//把起点初始化到有边的地方

    for(int i=1;i<=n;i++){

        sort(g[i].begin(),g[i].end(),cmp);

    }

    //保证了有解没必要去判断，直接找起点

    for(int i=1;i<=n;i++){

        if(degree[i]&1){

            start=i;

            break;

        }

    }

    

    dfs(start);

    

    while(top){

        printf("%d",s[top--]);

        if(top)printf("\n");

    }

    

}

POJ 1386-play on words

Description

Some of the secret doors contain a very interesting word puzzle. The team of archaeologists has to solve it to open that doors. Because there is no other way to open the doors, the puzzle is very important for us.

There is a large number of magnetic plates on every door. Every plate has one word written on it. The plates must be arranged into a sequence in such a way that every word begins with the same letter as the previous word ends. For example, the word ``acm'' can be followed by the word ``motorola''. Your task is to write a computer program that will read the list of words and determine whether it is possible to arrange all of the plates in a sequence (according to the given rule) and consequently to open the door.

Input

The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing a single integer number Nthat indicates the number of plates (1 <= N <= 100000). Then exactly Nlines follow, each containing a single word. Each word contains at least two and at most 1000 lowercase characters, that means only letters 'a' through 'z' will appear in the word. The same word may appear several times in the list.

Output

Your program has to determine whether it is possible to arrange all the plates in a sequence such that the first letter of each word is equal to the last letter of the previous word. All the plates from the list must be used, each exactly once. The words mentioned several times must be used that number of times.
If there exists such an ordering of plates, your program should print the sentence "Ordering is possible.". Otherwise, output the sentence "The door cannot be opened.".

题意翻译

输入n(n≤100000)个单词，是否可以把所有这些单词排成一个序列，使得每个单词的第一个字母可上一个单词的最后一个字母相同（例如acm,malform,mouse）。每个单词最多包含1000个小写字母。输入中可以有重复的单词。

代码：

#include <bits/stdc++.h>

using namespace std;

const int M=100010;

const int N=30;

int t;

int n,m;

//有向图的欧拉路径问题,需要记录入度和出度

int in[N];

int out[N];

//26个字母有可能有些不在图中，我们去标记下

int use[N];

//a-z看成26个点

//首字母xxxxxx尾字母

//一个单词看做是一个首字母连接到为字母的边

int p[N];

int find(int x){

    if(x!=p[x])p[x]=find(p[x]);

    return p[x];

}

void merge(int x,int y){

    int px=find(x),py=find(y);

    if(px==py)return ;

    p[px]=py;

}

int main(){

    scanf("%d",&t);

    char tmp[1001];

    while(t--){

        scanf("%d",&m);

        memset(in,0,sizeof in);

        memset(out,0,sizeof out);

        memset(use,0,sizeof use);

        memset(p,0,sizeof p);

        //连通性判断，直接使用并查集吧

        for(int i=0;i<26;i++)p[i]=i;

        while(m--){

            scanf("%s",tmp);

            int len=strlen(tmp);

            int u=tmp[0]-'a';

            int v=tmp[len-1]-'a';

            out[u]++;

            in[v]++;

            use[u]=use[v]=1;

            merge(u,v);

        }

        //判断欧拉路径

        //有向图的欧拉路径是入度和出度都相等or2个不等，一个出度大1的是start，另外一个是end

        int oddcnt=0;

        bool flag=true;

        int start=0;

        int end=0;

        for(int i=0;i<26;i++){

            if(!use[i])continue;

            if(in[i]!=out[i]){

                if(out[i]-in[i]==1)

                    start++;

                else if(out[i]-in[i]==-1)

                    end++;

                else

                    flag=false;

                oddcnt++;

            }

        }

        if(!((start==0&&end==0)||start==1&&end==1))flag=0;

        if(oddcnt!=0&&oddcnt!=2)flag=false;

        int lca=-1;

        for(int i=0;i<26;i++){

            if(!use[i])continue;

            int par=find(i);

            if(lca==-1)lca=par;

            else if(par!=lca){

                flag=false;

                break;

            }

        }

        if(!flag)printf("The door cannot be opened.");

        else printf("Ordering is possible.");

        if(t)printf("\n");

    }

}