题解：CF2056B Find the Permutation

· · 题解

简要说明题意：

有一个 1 到 n 的全排列 p，现在对所有的 1 \leq i<j \leq n,p_i<p_j，连一条 i,j 的无向边得到无向图

给出图求原排列 p。

题目分析：

我们可以想一下 1 \leq i<j \leq n,p_i<p_j 这个连边条件，它的意思是：每个数都要与更大且在右侧的数连边。

所有更大且在右侧的数都会被连边，并且所有更大且在左侧的数不会连边。

也就是说，可以通过每个数和更大的数的连接情况，得到每个数与更大的数的左右关系。

只要对所有的数都这么操作，我们可以得到所有数的左右关系（因为任意两个不相等的数都可以比出大小）。

根据所有数的左右关系还原原序列顺序，这个问题是拓扑排序板子。读入，建图和拓扑排序都是 O(\sum n^2)

代码如下：

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
string s;
bool map_[1001][1001];
int v[1001],last_[1001],next_[1000001],from_[1000001],to_[1000001],d[1001],cnt;
void link(int x,int y){
    from_[cnt]=x,to_[cnt]=y,next_[cnt]=last_[x],last_[x]=cnt++;
}
queue<int> q;
void toposort(int n){
    while(!q.empty()) q.pop();
    for(int i=1;i<=n;++i) if(!d[i]) q.push(i);
    int now,tot=0;
    while(!q.empty()){
        now=q.front(),q.pop(),v[tot++]=now;
        for(int i=last_[now];~i;i=next_[i]){
            --d[to_[i]];
            if(!d[to_[i]]) q.push(to_[i]);
        }
    }
}
int main(){
    int T,n;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n),fill(last_+1,last_+1+n,-1),fill(d+1,d+1+n,0),cnt=0;
        for(int i=1;i<=n;++i){
            cin>>s;
            for(int j=0;j<n;++j) map_[i][j+1]=(s[j]^'0');
        }
        for(int i=1;i<=n;++i) for(int j=i+1;j<=n;++j) map_[i][j]?(link(i,j),++d[j]):(link(j,i),++d[i]);
        toposort(n);
        for(int i=0;i<n;++i) printf("%d ",v[i]);
        putchar('\n');
    }
    return 0;
}