无序字母对-题解

查看题目请戳这里

又一道欧拉回路的裸题

把字母hash一下，然后跑一个欧拉回路就可以轻松搞定。 不会欧拉回路的戳这里。 附一下代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define INF 0x7fffffff
#define ll long long

using namespace std;
int n,m,x,y,tj,begin = INF,t,map[1000][1000],d[1000],sta[1000];
char s[2];
int getint(char c)
{
    if(c < ‘a’) return c - ‘A’ + 1;
    return c - ‘a’ + 27;
}
char getcha(int c)
{
    if(c <= 26) return c + ‘A’ - 1;
    return c + ‘a’ - 27;
}
void dfs(int k)
{
    for(register int i = 1; i <= n; i++)
    {
        if(map[k][i] > 0)
        {
            map[k][i] = 0;
            map[i][k] = 0;
            dfs(i);
        }
    }
    sta[++t] = k;
}
int main()
{
    scanf(“%d”,&m);
    for(register int i = 1; i <= m; i++)
    {
        cin >> s;
        x = getint(s[0]);
        y = getint(s[1]);
        n = max(x,n);
        n = max(y,n);
        begin = min(begin,x);
        begin = min(begin,y);
        map[x][y] = 1;
        map[y][x] = 1;
        d[x] ++;
        d[y] ++;
    }
    for(register int i = 1; i <= n; i++) if(d[i] % 2 == 1) tj ++;
    if(tj == 1 || tj >2)
    {
        printf(“No Solution\n”);
        return 0;
    }
    for(register int i = 1; i <= n; i++)
    {
        if(d[i] % 2 == 1)
        {
            begin = i;
            break;
        }
    }
    dfs(begin);
    int k = begin;
    for(register int i = t; i >0; i–) cout << getcha(sta[i]);
    cout << endl;
    return 0;
}