F. Chat Screenshots - 题解

比赛与标签

比赛: Codeforces Round 925 (Div. 3) 标签: combinatorics, dfs and similar, graphs, *1700 难度: *1700

喵~ 让我们先看看题目说了什么吧！

主人你好呀~ 这道题是关于聊天室里的成员排序问题，听起来很有趣对不对？

是这样的：一个聊天室里有 n 个小伙伴，他们有一个按“活跃度”排列的真实顺序。但是呢，每个人在自己的聊天界面里，看到的都是把自己放在列表的最顶端，其他人则保持原有的相对顺序。

比如说，真实的顺序是 [2, 3, 1, 4]。

1号小伙伴看到的列表就是 [1, 2, 3, 4]。（把1从原列表拿掉，剩下[2, 3, 4]，再把1放到最前面）
2号小伙伴看到的列表就是 [2, 3, 1, 4]。（把2从原列表拿掉，剩下[3, 1, 4]，再把2放到最前面）
...以此类推。

现在，有 k 个小伙伴把他们看到的列表截图发了出来。我们的任务就是判断，是否存在一个唯一的、共同的“真实顺序”，能够同时满足这 k 张截图的条件。如果存在，就输出 "YES"，否则就输出 "NO"。

解题思路喵~ 把关系变成图！

呐呐，主人，我们来分析一下，一张截图到底能告诉我们什么信息呢？

假设小猫A发了一张截图，他看到的顺序是 [A, p1, p2, p3, ..., pn-1]。根据题目的规则，这意味着在那个神秘的“真实顺序”里，p1 一定在 p2 的前面，p2 一定在 p3 的前面，以此类推。

这不就是一连串的偏序关系嘛！p1 必须先于 p2，p2 必须先于 p3...

当我们有多张截图时，我们就会得到很多这样的偏序关系。比如，一张截图告诉我们 B 必须在 C 前面，另一张截图可能告诉我们 C 必须在 D 前面。

如果某两张截图给出了矛盾的信息，比如一张说 B 在 C 前面，另一张又说 C 在 B 前面，那显然就不可能存在一个满足所有条件的真实顺序了，对吧？

这种“谁在谁前面”的依赖关系，是不是让你想到了什么？对啦！就是有向图！

我们可以把每个小伙伴看作图中的一个节点。如果小伙伴 u 必须在小伙伴 v 的前面，我们就从 u 向 v 连一条有向边 u -> v。

所以，我们的解题步骤就是：

建图：遍历 k 张截图。对于每张截图 [a, p1, p2, ..., pn-1]，我们从 p1 到 p2，p2 到 p3，...，pn-2 到 pn-1 依次连边。这样，所有截图提供的偏序关系都被我们转换成了图中的有向边。
判断合法性：建好图之后，问题就变成了：是否存在一个所有节点的线性排列，满足图中所有的有向边关系？这正是拓扑排序的定义！
寻找答案：一个有向图能够进行拓扑排序的充要条件是，它是一个有向无环图（DAG）。如果图中存在环，比如 u -> v -> w -> u，那就意味着 u 要在 v 前，v 要在 w 前，w 又要回到 u 前面。这就像小猫追自己的尾巴，永远也排不出一个确定的先后顺序！这种情况下，就不存在合法的真实顺序。

所以，我们的最终目标就是检查我们构建的图里有没有环。

我们可以用经典的 Kahn算法 来检测环并进行拓扑排序：

计算所有节点的入度（有多少条边指向它）。
把所有入度为 0 的节点放进一个队列里。
当队列不为空时，取出一个节点 u，将它加入拓扑序列，并把它所有的出边都“删掉”（也就是把它指向的邻居节点的入度减 1）。
如果某个邻居节点的入度在减 1 后变成了 0，就把它也加入队列。
重复这个过程，直到队列为空。

最后，我们检查一下加入拓扑序列的节点数量。如果数量等于总人数 n，说明所有节点都被成功排序，图中无环，答案就是 "YES"！如果数量小于 n，说明图中存在环，导致一些节点无法被处理，答案就是 "NO" 的说！

代码实现来啦~

cpp

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int main() {
    // 喵~ 这是一个小优化，让输入输出更快一点
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;

        // 用邻接表来存我们的小小关系图~
        vector<vector<int>> adj(n + 1);

        // 遍历 k 张截图来建立图的关系
        for (int i = 0; i < k; i++) {
            vector<int> a(n);
            for (int j = 0; j < n; j++) {
                cin >> a[j];
            }
            // 从截图的第二个元素开始，建立偏序关系
            // a[j] -> a[j+1]
            for (int j = 1; j < n - 1; j++) {
                adj[a[j]].push_back(a[j + 1]);
            }
        }

        // 去除重复的边，虽然不是必须的，但是个好习惯喵~
        for (int u = 1; u <= n; u++) {
            if (adj[u].size() > 1) {
                sort(adj[u].begin(), adj[u].end());
                auto last = unique(adj[u].begin(), adj[u].end());
                adj[u].erase(last, adj[u].end());
            }
        }

        // 计算每个小猫（节点）有多少条指向它的边（入度）
        vector<int> indegree(n + 1, 0);
        for (int u = 1; u <= n; u++) {
            for (int v : adj[u]) {
                indegree[v]++;
            }
        }

        // 准备一个队列，用于Kahn算法
        queue<int> q;
        // 把所有入度为0的节点（没有前置依赖的节点）放进队列
        for (int i = 1; i <= n; i++) {
            if (indegree[i] == 0) {
                q.push(i);
            }
        }

        // 记录拓扑排序能访问到的节点数量
        int count = 0;
        
        // 这是Kahn算法的核心部分哦~
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            count++; // 处理一个节点，计数器+1

            // 遍历这个节点的所有邻居
            for (int v : adj[u]) {
                indegree[v]--; // "删除" u->v 这条边
                // 如果邻居的入度也变成0了，那它也可以作为起点了，入队！
                if (indegree[v] == 0) {
                    q.push(v);
                }
            }
        }

        // 如果所有节点都被访问过，说明图中无环
        if (count == n) {
            cout << "YES\n";
        } else { // 否则，说明有环，无法完成拓扑排序
            cout << "NO\n";
        }
    }

    return 0;
}

复杂度分析时间~

时间复杂度: O(Σ(n * k)) 的说。对于每个测试用例，我们需要读取 k 张截图，每张截图有 n 个元素，这部分是 O(n * k)。然后建图，我们最多会添加 k * (n - 2) 条边。Kahn算法的复杂度是 O(V + E)，其中 V 是节点数(n)，E 是边数(最多 k * n)。所以单个测试用例的总复杂度是 O(n * k)。题目保证所有测试用例的 n * k 之和不超过 2 * 10^5，所以总的时间复杂度是线性的，非常高效！
空间复杂度: O(Σ(n * k)) 的说。我们主要的空间开销是邻接表 adj，它最多存储 k * (n-2) 条边。入度数组 indegree 和队列 q 的空间都是 O(n)。所以空间复杂度和边的数量级相同，也是 O(n * k)。

知识点与总结喵！

这道题真是一道非常经典的图论建模题呢！它教会了我们：

抽象问题: 将看似复杂的用户视图问题，抽象成了一系列简单的偏序关系。
图论建模: 把“偏序关系”或“依赖关系”转化为有向图中的边，是解决这类问题的关键一步。
拓扑排序: 判断是否存在一个满足所有依赖关系的全局序列，等价于判断图是否为有向无环图 (DAG)，而拓扑排序正是解决这个问题的标准武器！
Kahn算法: 它是实现拓扑排序和检测环的常用且高效的算法。

所以呀，主人~ 当你再遇到涉及“先后顺序”、“依赖关系”、“前提条件”这类问题时，一定要马上联想到拓扑排序哦！这是一种非常强大的思维工具呢。

继续加油，多练习，你一定能成为超厉害的算法大师的喵！(ฅ'ω'ฅ)

F. Chat Screenshots - 题解 ​

比赛与标签 ​

喵~ 让我们先看看题目说了什么吧！ ​

解题思路喵~ 把关系变成图！ ​

代码实现来啦~ ​

复杂度分析时间~ ​

知识点与总结喵！ ​