【洛谷P1341】无序字母对

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

题解：每个无需字母对可以看成无向图中的一条边。因此，题目中让构造的就是一个欧拉路（路径或回路均可），即：无向图中的每条边恰好经过一次的路径。存在欧拉路的充要条件是：无向图联通，且每个顶点的度均为偶数有且仅有两个顶点的度为奇数。

代码如下

#include <bits/stdc++.h>

using namespace std;

const int maxn=151;

bool G[maxn][maxn];

int n,f[maxn],deg[maxn];

char ch[5],stk[maxn<<2];

inline int find(int x){

    return x==f[x]?f[x]:f[x]=find(f[x]);

}

void read_and_parse(){

    scanf("%d",&n);

    for(int i=1;i<=150;i++)f[i]=i;

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

        scanf("%s",ch+1);

        G[ch[1]][ch[2]]=G[ch[2]][ch[1]]=1;

        f[find(ch[1])]=find(ch[2]);

        ++deg[ch[1]],++deg[ch[2]];

    }

}

void dfs(int u){

    for(int i=1;i<=150;i++)if(G[u][i]){

        G[u][i]=G[i][u]=0;

        dfs(i);

    }

    stk[n--]=u;

}

void solve(){

    int cnt=0,st=0;

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

    if(cnt!=1){puts("No Solution");return;}

    cnt=0;

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

        if(deg[i]&1){

            ++cnt;

            if(!st)st=i;

        }

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

    if(cnt&&cnt!=2){puts("No Solution");return;}

    dfs(st);

    puts(stk);

}

int main(){

    read_and_parse();

    solve();

    return 0;

}

巴特西

【洛谷P1341】无序字母对

最新文章

热门文章