题解：CF2056B Find the Permutation

lgx57 · 2025-01-19 22:19:42 · 题解

拓扑排序模板题。

用 p_i 与 p_j 的关系建图。如果 g_{i,j}=1，那么连 i \to j，否则连 j \to i。然后拓扑排序。答案即为排序后的顺序。

void sol(){
    int n;
    cin>>n;
    for (int i=1;i<=n;i++){
        deg[i]=0;
        p[i].clear();
        for (int j=1;j<=n;j++){
            char c;
            cin>>c;
            a[i][j]=c-'0';
        }
    }
    for (int i=1;i<=n;i++){
        for (int j=i+1;j<=n;j++){
            if (a[i][j]) p[i].pb(j),deg[j]++;
            else p[j].pb(i),deg[i]++;
        }
    }
    queue<int> q;
    for (int i=1;i<=n;i++) if (!deg[i]) q.push(i);
    while (!q.empty()){
        int u=q.front();
        q.pop();
        cout<<u<<' ';
        for (int v:p[u]){
            if (!(--deg[v])) q.push(v);
        }
    }
    cout<<endl;
}