无序字母对 character

无序字母对 character

题目描述

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

输入

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

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

输出

输出满足要求的字符串。 

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

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

---

solution

把关系看做边，问题转化求一条边不重复的路径，即欧拉路径，也可以是回路。

先判断有没有两个奇点。

Hierholzer算法

循环寻找与x相连的边(x,u):删边

Hierholzer(u);

将x插入栈之中

这样可以保证找到的一定是第一条合法的路

因为删完边就走不出去了

倒序输出答案

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<queue>

#define maxn 3005

using namespace std;

int n,head[maxn],in[maxn],flag[maxn],ae,tot,st;

char ch[maxn],s[maxn][maxn];

struct node{

    char t1,t2;

}e[4005];

void dfs(char t){

    for(int i='A';i<='z';i++){

        if(s[t][i]){s[t][i]=s[i][t]=0;dfs(i);}

    }

    ch[n--]=t;

}

int main()

{

    cin>>n;

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

        scanf(" %c %c",&e[i].t1,&e[i].t2);

        if(e[i].t1>e[i].t2)swap(e[i].t1,e[i].t2);

        s[e[i].t1][e[i].t2]=s[e[i].t2][e[i].t1]=1;

        st=e[i].t1;

        in[e[i].t1]++;in[e[i].t2]++;

    }

    int cnt=0;

    for(int i='A';i<='z';i++){

        if(in[i]&1){cnt++;if(cnt==1)st=i;}

    }

    if(cnt==0||cnt==2)dfs(st);

    else puts("No Solution");

    puts(ch);

    return 0;

}