M_sea

洛谷P1341 无序字母对
Luogu算法建图求欧拉路即可。代码#include <bits/stdc++.h> #define ...
扫描右侧二维码阅读全文
17
2018/07

洛谷P1341 无序字母对

Luogu

算法

建图求欧拉路即可。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

const int MAXN=256;
int G[MAXN][MAXN];
int degree[MAXN];
char ans[MAXN*MAXN];
char tmp[MAXN];
int n;

inline void Hierholzer(int u) {
    for (re int v=0;v<MAXN;v++)
        if (G[u][v]) {
            G[u][v]=G[v][u]=0;
            Hierholzer(v);
        }
    ans[n--]=u;
}

int main() {
    ios::sync_with_stdio(false);
    cin>>n;
    for (re int i=1;i<=n;i++) {
        cin>>tmp;
        G[tmp[0]][tmp[1]]=G[tmp[1]][tmp[0]]=1;
        degree[tmp[0]]++; degree[tmp[1]]++;
    }
    char s=0; int cnt=0;
    for (re int i=0;i<MAXN;i++) {
        if (degree[i]&1) {
            cnt++;
            if (!s) s=i;
        }
    }
    if (!s) {
        for (re int i=0;i<MAXN;i++)
            if (degree[i]) { s=i; break; }
    }
    if (cnt!=0&&cnt!=2) { puts("No Solution"); return 0; }
    Hierholzer(s);
    puts(ans);
    return 0;
}
最后修改:2019 年 05 月 26 日 02 : 33 PM

发表评论