acm-(好题、拓扑序、并查集)Educational Codeforces Round 100 (Rated for Div. 2) E. Plan of Lectures_e - plan of lectures

传送门
首先这$k$对两元组可以形成若干条链或者环，当然如果形成了环就不合法了，特别地，我们把所有不在这$k$对二元组中的点也看成是长度为1的链。

要输出一个合法的解就得保证链条按照拓扑序被一条条输出。

首先利用并查集将同一条链的所有点放入并查集。
然后写一个$check$函数来检查链条的合法性，合法性即不能拥有环以及链条上不能出现违背拓扑序的情况(具体实现的时候，$check$函数只检查链条的每个连通块中是否存在违背拓扑序的情况，块与块之间违背拓扑序的情况则会在下一部分自动被处理)。在检查合法性的过程中，还要维护出每条链在树上有多少个连通块(代码中用$sz$表示)，不同的连通块在树上没有直接的边相连。

然后用$deque$来遍历树，对于一条链而言，只有当它的所有连通块都被访问到后，才可以将链头$push\_back$进入队列，这意味着如果同一条链上有两个连通块具有拓扑序关系(不管是否逆拓扑序)，那么这条链永远不可能被放入队列，因此这种不合法的情况可以被考虑到(对于一条链来说它的每个连通块一定不能存在拓扑关系，否则这条链就不能被连续的放进答案的序列中了)。而对于当前的队头我们总是会考虑它的后继是否存在，如果存在就将后继也放入队头，因为当前链的优先级总是最高的。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 3e5+5;

vector<int>g[maxn];

int n,k,fa[maxn],nxt[maxn],vis[maxn],sz[maxn];

int fd(int rt){
    return rt==fa[rt]?rt:(fa[rt]=fd(fa[rt]));
}
bool check(){//判断k对是否合法，如果存在环或者违背拓扑序，那么就不合法
    for(int i=1;i<=n;++i){
        if(!vis[fd(i)]){
            int u=fd(i);
            while(nxt[u]){
                if(vis[u])return false;//存在环
                vis[u]=1;
                for(int j=0;j<g[u].size();++j){
                    int v=g[u][j];
                    if(fd(v)!=fd(u))continue;
                    if(vis[v])return false;//违背拓扑序
                    else sz[fd(v)]--;//连通块--
                }
                u=nxt[u];
            }
        }
    }
    return true;
}
deque<int>q;
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i){
        int u;
        fa[i]=i;
        sz[i]=1;
        scanf("%d",&u);
        g[u].push_back(i);
    }
    for(int i=1;i<=k;++i){
        int x,y;
        scanf("%d%d",&x,&y);
        nxt[x]=y;
        sz[fd(x)]+=sz[fd(y)];
        fa[fd(y)]=fd(x);
    }
    if(!check())return printf("0\n"),0;
    vector<int>ans;
    q.push_back(0);
    memset(vis,0,sizeof(int)*(n+1));
    while(!q.empty()){
        int u=q.front();q.pop_front();
        if(u)ans.push_back(u);
        if(nxt[u])q.push_front(nxt[u]);//当前链的优先级永远是最高的
        for(int i=0;i<g[u].size();++i){
            int v=g[u][i];
            if(!vis[fd(v)])sz[fd(v)]--;
            if(!sz[fd(v)] && !vis[fd(v)])q.push_back(fd(v)),vis[fd(v)]=1;//如果这条链的所有连通块均被访问了，那么就将链头push到队头
        }
    }
    if((int)ans.size()==n){
        for(int i=0;i<ans.size();++i)printf("%d ",ans[i]);
        puts("");
    }else printf("0\n");//如果有些链没有被访问(没被访问的原因在于与另外的链发生了拓扑序上的交叉，导致没有一个链能够被访问)，那么无解
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69