1 条题解

  • 0
    @ 2025-7-18 14:38:11
    #include <bits/stdc++.h>
    using namespace std;
    int n, m;
    int u[605], v[605];
    // 通过前 x 条关系,能否确定顺序
    // 0:无法确定,1:可以确定,2:存在矛盾
    int d[30];
    queue<int> q;
    vector<int> e[30];
    string s;
    int check(int x)
    {
        // 清空所有东西
        for (int i = 1; i <= n; i++)
        {
            d[i] = 0;
            e[i].clear();
        }
        while (!q.empty())
            q.pop();
        s = "";
        // 前 x 条边加入图
        for (int i = 1; i <= x; i++)
        {
            e[u[i]].push_back(v[i]);
            d[v[i]]++;
        }
        // 拓扑排序
        bool flag = false; // 多解标记
        // 1. 所有入度为 0 的点作为起点
        for (int i = 1; i <= n; i++)
            if (d[i] == 0)
                q.push(i);
        // 2. 类似与广搜的扩展
        while (!q.empty())
        {
            // 有多解
            if (q.size() > 1)
                flag = true;
            // 正常扩展
            int now = q.front();
            q.pop();
            // 记录答案
            s = s + (char)(now - 1 + 'A');
            for (int i = 0; i < e[now].size(); i++)
            {
                int nxt = e[now][i];
                d[nxt]--;
                if (d[nxt] == 0)
                    q.push(nxt);
            }
        }
        if (s.size() != n)
            return 2; // 存在矛盾
        if (flag)
            return 0; // 无法确定
        // 没有多解和矛盾的时候,你当前的解才是唯一解
        return 1;
    }
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin >> n >> m;
        for (int i = 1; i <= m; i++)
        {
            string s;
            cin >> s;
            if (s[1] == '<')
                u[i] = s[0] - 'A' + 1,
                v[i] = s[2] - 'A' + 1;
            else
                v[i] = s[0] - 'A' + 1,
                u[i] = s[2] - 'A' + 1;
        }
        for (int i = 1; i <= m; i++)
        {
            int res = check(i);
            if (res == 1)
            {
                cout << "Sorted sequence determined after " << i << " relations: " << s << ".";
                return 0;
            }
            if (res == 2)
            {
                cout << "Inconsistency found after " << i << " relations.";
                return 0;
            }
        }
        cout << "Sorted sequence cannot be determined.";
        return 0;
    }
    

    信息

    ID
    2156
    时间
    1000ms
    内存
    125MiB
    难度
    4
    标签
    递交数
    8
    已通过
    4
    上传者