P1341 无序字母对

题目描述

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

输入输出格式

输入格式：

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

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

输出格式：

输出满足要求的字符串。

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

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

说明

【数据规模与约定】

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

---

其实比较裸

先存储，然后对边排序。注意用前向星的话，从大的边往小的边加。然后直接跑欧拉路即可。

和这个题是差不多的。

---

Code：

#include <cstdio>

#include <iostream>

#include <cstdlib>

#include <algorithm>

using namespace std;

const int N=130;

const int M=10010;

int head[N],to[M],next[M],cnt=1;

void add(int u,int v)

{

    next[++cnt]=head[u];to[cnt]=v;head[u]=cnt;

    next[++cnt]=head[v];to[cnt]=u;head[v]=cnt;

}

pair <int ,int > edge[M];

int S=N,in[N],n;

void init()

{

    scanf("%d",&n);

    char u,v;

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

    {

        scanf("\n");

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

        if(u>v) swap(u,v);

        edge[i].first=u,edge[i].second=v;

        in[u]++;in[v]++;

        S=S>u?u:S;

    }

    int cnt0=0;

    for(int i='z';i>='A';i--)

        if(in[i]&1)

            S=i,cnt0++;

    if(cnt0>2)

    {

        printf("No Solution\n");

        exit(0);

    }

    sort(edge+1,edge+1+n);

    for(int i=n;i;i--)

        add(edge[i].first,edge[i].second);

}

int s[M],tot,vis[M];

void dfs(int now)

{

    for(int i=head[now];i;i=next[i])

    {

        if(!vis[i])

        {

            vis[i]=vis[i^1]=1;

            head[now]=next[i];

            dfs(to[i]);

        }

    }

    s[++tot]=now;

}

void work()

{

    dfs(S);

    for(int i=tot;i;i--)

        printf("%c",s[i]);

}

int main()

{

    init();

    work();

    return 0;

}

---

2018.7.4