P1341 无序字母对（欧拉回路）

题目链接：

https://www.luogu.org/problemnew/show/P1341

题目描述

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

输入输出格式

输入格式：

第一行输入一个正整数n。

以下n行每行两个字母，表示这两个字母需要相邻。

输出格式：

输出满足要求的字符串。

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

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

输入输出样例

输入样例#1：

4

aZ

tZ

Xt

aX

输出样例#1：

XaZtX

解题思路：

非常有意思的一道题，主要考察欧拉回路和欧拉路径的运用。

1，首先针对题目样例，输出样例不是aXtZa，因为'a'的ascii码是97,'X'的ascii码是88。

2，将每一个字符看做一个孤立的点，利用输入的数据建立无向图，如果图连通并且存在欧拉回路(每个节点的度数均为偶数)或者存在欧拉路径(仅存在两个点的度数是奇数，其余点的度数均为偶数)，则满足题目要求，再从头dfs一遍记录结果即可。

欧拉回路：通过所有边一次且仅一次，最终回到出发点的路（每个节点的度数均为偶数）

欧拉路径：通过所有边一次且仅一次，最终不回到出发点的路（仅存在两个点的度数是奇数，其余点的度数均为偶数）

#include <iostream>

#include<cstdio>

#include<cstring>

#include<string>

using namespace std;

int f[125];

int ed[125][125];

int deg[125];

int ans[1000010];

int n;

//A 65 z 122

int findroot(int x){//并查集判连通

    if(x==f[x]) return x;

    return f[x]=findroot(f[x]);

}

void dfs(int k){//记录路径

    for(int i=65;i<=122;i++){

        if(ed[k][i]){

            ed[k][i]=ed[i][k]=0;

            dfs(i);

        }

    }

    ans[n--]=k;

}

int main(int argc, char** argv) {

    scanf("%d",&n);

    int m=n;

    memset(ed,0,sizeof(ed));

    for(int i=65;i<=122;i++) f[i]=i;

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

        string s;cin>>s;

        ed[s[0]][s[1]]=ed[s[1]][s[0]]=1;

        deg[s[0]]++;deg[s[1]]++; 

        int x=findroot(s[0]),y=findroot(s[1]);

        if(x!=y) f[x]=y;

    }

    int cnt=0;

    for(int i=65;i<=122;i++) if(f[i]==i&&deg[i]) cnt++;

    if(cnt!=1) {printf("No Solution\n");return 0;}//图不连通，退出

    int st=0;

    cnt=0;

    for(int i=65;i<=122;i++){

        if(deg[i]&1){

            cnt++;

            if(!st) st=i;

        }

    }

    if(cnt>2) {printf("No Solution\n");return 0;}//不满足欧拉路径，退出

    if(!st){//不存在欧拉路径，但存在欧拉回路

        for(int i=65;i<=122;i++) if(!(deg[i]&1)&&deg[i]) {st=i;break;}

    }

    dfs(st);

    for(int i=0;i<=m;i++) printf("%c",ans[i]-65+'A');

    return 0;

}

巴特西