P1137 旅行计划

· · 题解

P1137 旅行计划

题目翻译：

给你一个图，求出每一个点西方有多少点可以到

思路：

我们可以发现，要求只能从西往东走，着可以发现这就是一个拓扑排序的过程，但要求出西方有多少个点，这我们可以给每一个节点设置一编号，及他前方点的个数（答案），在拓扑一个新的入度为零的点将他的值改成前面点的值加一即可

完整代码：

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
vector<int>e[N];
int in[N],d[N];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        in[v]++;
    }
    vector<int>ans;
    queue<int>q;
    for(int i=1;i<=n;i++){
        if(!in[i]){
            q.push(i);
        }
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        ans.push_back(u);
        for(auto it:e[u]){
            in[it]--;
            if(!in[it]){
                q.push(it);
                d[it]=d[u]+1;
            }
        }
    }
    for(int i=1;i<=n;i++){
        cout<<d[i]+1<<endl;
    }
}

拓扑排序讲解