Codeforces 1463 E. Plan of Lectures（缩点，拓扑排序）

83 阅读 0 评论 55 点赞

我是靠谱客的博主文艺黄豆，最近开发中收集的这篇文章主要介绍Codeforces 1463 E. Plan of Lectures（缩点，拓扑排序），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：
要求你构造一个 $n$ 的排列，要满足：

$a [i]$ 出现在 $i$ 之前，如果 $a [i] = 0$ 代表这个数没有限制。仅对条件一保证一定有解。
有 $k$ 个特殊对 $(i, j)$ ，要求满足 $i$ 在排列中一定在 $j$ 的左边。

询问是否存在这样的排列。

思路：
这场的 $E$ 题简单的贪心和模拟就可以解决XD。

假设没有特殊对，那么直接按照条件1的限制跑一次拓扑排序（条件一实际构成了一个DAG图）。
有特殊对后，因为特殊对是要排列在一起的，所以不妨直接并查集缩点。将这些特殊对当做一个点再建图跑拓扑排序。然后对于每个点再按照之前在特殊对中的次序展开。
那么咋判断无解的情况呢？因为原本就是一个DAG图，所以新的图中也不应该出现环（出现了就无解）。那么无解就是特殊对构成的次序有环，或者特殊对的次序不满足条件一的限制。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

const int maxn = 3e5 + 7;
int nex[maxn],fa[maxn],deg[maxn];
int cnt,pos[maxn];
vector<int>G[maxn],a,ans;
int findset(int x) {
    if(fa[x] == x) {
        return x;
    }
    return fa[x] = findset(fa[x]);
}
void Union(int x,int y) {
    int rx = findset(x),ry = findset(y);
    if(rx != ry) {
        fa[ry] = rx;
    }
}
void bfs(int x) {
    queue<int>q;
    q.push(x);
    ans.push_back(x);
    while(!q.empty()) {
        int now = q.front();q.pop();
        for(int i = 0;i < G[now].size();i++) {
            int v = G[now][i];
            deg[v]--;
            if(deg[v] == 0) {
                q.push(v);
                ans.push_back(v);
            }
        }
    }
}

int main() {
    int n,k;scanf("%d%d",&n,&k);
    int root = 0;
    for(int i = 1;i <= n;i++) {
        int x;scanf("%d",&x);
        fa[i] = i;
        if(x == 0) root = i;
        a.push_back(x);
    }
    for(int i = 1;i <= k;i++) {
        int x,y;scanf("%d%d",&x,&y);
        nex[x] = y;
        Union(x,y);
    }
    for(int i = 1;i <= n;i++) {
        int x = findset(a[i - 1]),y = findset(i);
        if(x == y) continue;
        G[x].push_back(y);
        deg[y]++;
    }
    for(int i = 1;i <= n;i++) {
        if(i == findset(i)) {
            cnt++;
        }
    }
    
    root = findset(root);
    bfs(root);
    vector<int>res;
    for(int i = 0;i < ans.size();i++) {
        int now = ans[i];
        for(int j = now;j;j = nex[j]) {
            res.push_back(j);
            if(res.size() > n) {
                printf("0n");
                return 0;
            }
        }
    }
    for(int i = 0;i < res.size();i++) {
        pos[res[i]] = i;
    }
    for(int i = 1;i <= n;i++) {
        int x = a[i - 1],y = i;
        if(pos[x] > pos[y]) {
            printf("0n");
            return 0;
        }
    }
    for(int i = 0;i < res.size();i++) {
        printf("%d ",res[i]);
    }
    return 0;
}