相对次序建有向图——cf_925_F. Chat Screenshots

• 问题概述
• 思路分析
• 参考代码
• 做题反思

问题概述

原题参考:F. Chat Screenshots
聊天室内有n个人，存在一定的顺序，但是每个人看顺序时都会把自己放到最前面，其余人的位置不变，现在给出k组长度为n的排列，问是否冲突

思路分析

对于k组排列，除了自己的位置未知外，其余人的相对次序都是正确的，将其看作有向边，如果出现矛盾，则会成环，因此对于该问题，就是将k组排列的相关边建图，然后求拓扑排序

参考代码

#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define pll pair<long long, long long>
#define pii pair<int, int>
#define vi vector<int>
#define vl vector<long long>
#define ll long long
#define ull unsigned long long
const ll INF = 9187201950435737471;
const int inf = 2139062143;
const ll mod = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1.0);
const int N = 2e5+7;
vi e[N];
int n, m, dIn[N], mq[N];
void topoSort() {
    int front = 1, rear = 0;
    for(int i=1; i<=n; i++) {
        if(!dIn[i]) mq[++rear] = i;
    }
    while(front <= rear) {
        int cur = mq[front++];
        for(auto nxt:e[cur]) {
            if(!(--dIn[nxt])) mq[++rear] = nxt;
        }
    }
    if(front == n+1) cout << "YES" << endl;
    else cout << "NO" << endl;
}
void solve() {
    cin >> n >> m;
    while(m --) {
        int pre = 0, now;
        for(int i=1; i<=n; i++) {
            cin >> now;
            if(i == 1) continue;
            if(!pre) pre = now;
            else {
                e[now].push_back(pre);
                dIn[pre]++;
                pre = now;
            }
        }
    }
    topoSort();
    for(int i=1; i<=n; i++) dIn[i] = 0, e[i].clear();
}
int main() {
#ifdef xrl
    freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout);
#endif
    FAST_IO;
    int t = 1;
    cin >> t;
    while(t --) solve();
#ifdef xrl
    cout << "Time used = " << (double)(clock() * 1.0 / CLOCKS_PER_SEC) << "s";
#endif
    return 0;
}

做题反思

都没想到这一茬，甚至还想着模拟来着