题解P1137【旅行计划】（拓扑排序）

以前都一直不懂拓扑排序是个什么东西，看了一下发现还是蛮简单的 拓扑排序是给一个有向无环图（DAG）上的点进行排序，排成线性序列，使排序后的点满足所有的边u->v，在这个序列中，u都在v的前面。 如果还是没明白的话，来举个栗子，如下图  序列v6–>v1—->v4—>v3—>v5—>v2就是一个满足拓扑排序要求的序列，当然v1–>v6—->v4—>v3—>v5—>v2，也是可以的 具体怎么做呢？首先找到入度为0的点。因为入度为0的点肯定排在最前面，任意去掉一个入度为0的点和它的边，再次统计入度为0的点并重复这个过程，像这样：  我们先去掉了v6，这时入度为0的点只剩下v1，所以再去掉v1  这时v3,v4都可以去掉，我们去掉v4  然后再是v3  再是v5，v2，就得到了v6–>v1—->v4—>v3—>v5—>v2这个序列 最后得到的序列会因程序而异。 ------------ ------------ ## 题解部分 很明显这题可以用拓扑排序，只需要记录一下每个点是第几轮被去掉的就可以了。因为第几轮被去掉就代表了它之前有几个点过来。这里的一轮是指所有入度为0的点同一时间去掉算一轮。具体看代码吧。 ```cpp #include<cstdio> #include<cstring> #include<iostream> using namespace std; int n,m,cnt=0; int head[200100],nxt[200100],to[200100]; int in[100100],ans[100100]; int q[100100],f[100100]; void addedge(int x,int y) { cnt++; nxt[cnt]=head[x]; head[x]=cnt; to[cnt]=y; } void tpsort() { int l=0,r=0; for(int i=1;i<=n;i++) if(in[i]==0) q[++r]=i,f[i]=1;//先将入度为0的点进队列，并且记录下这些点将在第一轮被去掉。 while(l<=r) { int u=q[++l]; for(int i=head[u];i!=-1;i=nxt[i]) { int v=to[i]; if(f[v]) continue; in[v]--;//去掉与这个点有关的边，相连的点的入度减1 if(in[v]==0) {//如果相连的点入度为0了，进队列，进行删点 f[v]=f[u]+1;//可以说是一个小小的DP，这个点必然是在当前点的后一轮删除的 q[++r]=v; } } } } int main() { memset(in,0,sizeof(in)); memset(head,-1,sizeof(head)); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); addedge(x,y);//加边 in[y]++;//记录入度 } tpsort(); for(int i=1;i<=n;i++) cout<<f[i]<<endl; return 0; } ```