洛谷 P1341 无序字母对 题解【欧拉路】【字符串】

点击量：189

    字符串比较好处理，主要是字典序和欧拉路的问题。

目录

题目描述

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

 

输入输出格式

输入格式：

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

 

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

 

输出格式：

输出满足要求的字符串。

 

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

 

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

 

输入输出样例

输入样例#1：

4

aZ

tZ

Xt

aX

输出样例#1：

XaZtX

说明

【数据规模与约定】

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

题解：

   首先每对字母只能出现一次，因此本题需要求字母构建的图所形成的欧拉路，且要求字典序最小。我们首先用字符的ASCII码直接访问到65至122（’A’到’z’），构建出图，再找到ASCII码最小的度为奇数的点，如果没有度为奇数的点，就找最小的在图上的字母，开始访问。

   题目构思在学了欧拉路后不难，但是要注意一点的是链表建图的问题。在这里我用到了构建双向边的指针链表，因为要保证字典序，所以按顺序插入，链表是比较稳定的。然而这里会出现自环，类似”AA”这样的字符串，这样一来，自己再去指自己的尾巴，就会导致出现缺省值NULL的情况。这里是学习链表要注意的情况。当然，用前向星从大到小排序也是可以轻便地完成的。

Code：

#include<cstdio>
#include<cstring>
#include<algorithm>
using std::sort;
using std::min;
using std::max;
struct node
{
    int n;
    bool used;
    node *nxt,*op;
    node(int n)
    {
        this->n=n;
        nxt=NULL;
        op=NULL;
        used=false;
    }
    node()
    {
        nxt=NULL;
        op=NULL;
        used=false;
    }
};
node head[256],*tail[256];
struct edge
{
    int x,y;
    friend bool operator <(edge a,edge b)
    {
        if(a.x!=b.x)
            return a.x<b.x;
        return a.y<b.y;
    }
}e[20000];
int d[256];
int S[20000],top=0;
void dfs(int x)
{
    node *p=&head[x];
    while(p->nxt!=NULL)
    {
        p=p->nxt;
        if(!p->used)
        {
            p->used=true;
            p->op->used=true;
            head[x]=*p;
            dfs(p->n);
            S[++top]=p->n;
            p=&head[x];
        }
    }
    return;
}
int main()
{
    memset(d,0,sizeof(d));
    for(int i='A';i<='z';i++)
        tail[i]=&head[i];
    int n;
    char c[5];
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",c);
        e[i].x=min(c[0],c[1]);
        e[i].y=max(c[0],c[1]);
        d[c[0]]++;
        d[c[1]]++;
    }
    int sum=0,s=0;
    for(int i='z';i>='A';i--)
        if(d[i]&1)
        {
            sum++;
            s=i;
        }
    if(s==0)
        for(int i='A';i<='z';i++)
            if(d[i])
            {
                s=i;
                break;
            }
    if(sum>2)
    {
        puts("No Solution");
        return 0;
    }
    sort(e+1,e+1+n);
    for(int i=1;i<=n;i++)
    {
        tail[e[i].x]->nxt=new node(e[i].y);
        tail[e[i].x]=tail[e[i].x]->nxt;
        if(e[i].x!=e[i].y)//这里要注意，自环在这个题里基本可以忽略
        {
            tail[e[i].y]->nxt=new node(e[i].x);
            tail[e[i].y]=tail[e[i].y]->nxt;
        }
        tail[e[i].x]->op=tail[e[i].y];
        tail[e[i].y]->op=tail[e[i].x];
    }
    dfs(s);
    S[++top]=s;
    for(int i=top;i;i--)
        printf("%c",S[i]);
    return 0;
}