字典序的疑问
查看原帖
字典序的疑问
833124
BIOS楼主2023/6/17 19:36
#include <iostream>
#include <cstring>
using namespace std;
const int M = 1e6 + 5;
char s[2];
int m, n, ans[M], d[100], p[100], a, b, cnt, g[100][100];
bool st[100];
int find(int x)
{
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}
bool check()
{
    int q = -1;
    for (int i = 0; i < 100; i++)
        if (st[i])
            if (q == -1)
                q = find(i);
            else if (q != find(i))
                return false;
    int sum = 0;
    for (int i = 0; i < 100; i++)
        if (d[i] & 1)
            sum++;
    if (sum == 0 || sum == 2)
        return true;
    else
        return false;
}
void dfs(int u)
{
    for (int i = 0; i < 100; i++)
        if (g[u][i])
            g[u][i]--, g[i][u]--, dfs(i);
    ans[++cnt] = u;
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> m;
    for (int i = 0; i < 100; i++)
        p[i] = i;
    while (m--)
    {
        cin >> s;
        a = s[0] - 'A', b = s[1] - 'A';
        g[a][b]++, g[b][a]++, st[a] = st[b] = true, d[a]++, d[b]++;
        a = find(a), b = find(b);
        if (a != b)
            p[a] = b;
    }
    if (check())
    {
        int start = 0;
        while (!d[start])
            start++;
        dfs(start);
        for (int i = cnt; i; i--)
            printf("%c", ans[i] + 65);
        puts("");
    }
    else
        puts("No Solution");
}

题目说尽可能输出前面字母ASCII码更小的,对于同样一组输入,我的输出是“CvXggwPplcI”,测试点输出是“IcCvXggwPpl”,难道C不比I小吗

2023/6/17 19:36
加载中...