历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 1191. $\Large\color{blue}{【算法基础课】家谱树（拓扑排序）}$ 原题链接简单

作者：

incra , 2022-11-13 14:21:13 , 所有人可见 , 阅读 1419

<—点个赞吧QwQ

宣传一下算法提高课整理{:target=”_blank”}

有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。

给出每个人的孩子的信息。

输出一个序列，使得每个人的孩子都比那个人后列出。

输入格式

第 $1$ 行一个整数 $n$ ，表示家族的人数；

接下来 $n$ 行，第 $i$ 行描述第 $i$ 个人的孩子；

每行最后是 $0$ 表示描述完毕。

每个人的编号从 $1$ 到 $n$ 。

输出格式

输出一个序列，使得每个人的孩子都比那个人后列出；

数据保证一定有解，如果有多解输出任意一解。

数据范围

$1 \\le n \\le 100$

输入样例：

输出样例：

2 4 5 3 1

思路

看完这题，这不就是拓扑排序的模板题吗？啪的一下敲好—— $AC$ ！

思想：不断选择入度为 $0$ 的点 $x$ ，把 $x$ 连向的点的入度 $-1$ 。
可以结合 bfs 的框架来高效实现这个过程：

建立空的拓扑序列 $A$ .
预处理所有点的入度 $deg[i]$ , 起初把所有入度为 $0$ 的点入队。
取出队头节点 $x$ , 把 $x$ 加入拓扑序列 $A$ 的末尾。
对于从 $x$ 出发的每条边 $\lt x, y\gt$ , 把 $deg[y]- -$ 。若被减为 $0$ ，则把 $y$ 入队。
重复第 $3 \sim 4$ 步直到队列为空，此时 $A$ 即为所求。

拓扑排序可以判断有向图是否存在环。我们可以对任意有向图执行上述过程，在完成后检查 $A$ 序列的长度。若 $A$ 序列的长度小于图中点的数量，则说明某些节点未被遍历，进而说明图中存在环。

#include <iostream>
#include <cstring>
using namespace std;
const int N = 110,M = N * N;
int n;
int h[N],e[M],ne[M],idx;
int in_deg[N];
int q[N],hh,tt;
void add (int a,int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
void top_sort () {
    tt = -1;
    for (int i = 1;i <= n;i++) {
        if (!in_deg[i]) q[++tt] = i;
    }
    while (hh <= tt) {
        int t = q[hh++];
        for (int i = h[t];~i;i = ne[i]) {
            int j = e[i];
            in_deg[j]--;
            if (!in_deg[j]) q[++tt] = j;
        }
    }
}
int main () {
    memset (h,-1,sizeof (h));
    cin >> n;
    for (int i = 1;i <= n;i++) {
        int x;
        while (cin >> x,x) {
            add (i,x);
            in_deg[x]++;
        }
    }
    top_sort ();
    for (int i = 0;i < n;i++) cout << q[i] << ' ';
    return 0;
}

8 评论

legola 2023-03-19 18:20

还不会拓扑排序的伙伴们看下这篇博客，感觉讲得很好！

西望云天 2025-04-09 13:03 · 新疆

感觉比较清晰

#include<bits/stdc++.h>
//拓扑排序 解决终点在起点之后的排序问题 
using namespace std;

const int N = 110;
int in_du[N];
vector<int>adj[N];
int n, x;
void top_sort(){
    queue<int>q;
    for(int i = 1 ; i <= n ; i ++){
        if(in_du[i] == 0 ){  // 只要入度为零就加入队列 ， 队列的顺序就是拓扑排序的顺序
            q.push(i);
        }
    }
    while(!q.empty()){
        int t = q.front();
        q.pop();
        cout << t <<" ";
        for(auto j : adj[t]){
            in_du[j]--;
            if(in_du[j] == 0 )q.push(j);
        } 
    }
} 

int main(){

    cin >> n ;
    for( int i  = 1 ;  i <= n ; i ++){
        for(int j = 1 ;; j ++){
            cin >> x;
            if( !x) break;
            in_du[x]++;
            adj[i].push_back(x);
        }
    } 
    top_sort();
    return 0;
}

baikun 2023-12-18 10:20

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


const int N=80;
int e[N],ne[N],h[N],w[N],in[N],inn[N];
int f[N],p[N];
int idx,s,sum,v,unpd;
//路径期望 
int n,m;
queue<int> q;
int cnt=0;
int ans[N];

void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx;
    idx++;
}



void topsort(){
    queue<int> q;
    for(int i=1;i<=n;i++){
        if(in[i]==0){
            q.push(i);
            ans[++cnt]=i;
        }
    }
    while(q.size()){
        int t=q.front();
        q.pop();
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            in[j]--;
            if(in[j]==0){
                q.push(j);
                ans[++cnt]=j;
            }

        }
    }

    for(int i=1;i<=n;i++){
        cout<<ans[i]<<" ";
    }


}





int main(){
    memset(h,-1,sizeof h);
    cin>>n;
    for(int i=1;i<=n;i++){
        while(cin>>m&&m){
            add(i,m);
            in[m]++;
        }
    }
    topsort();
}