当前位置：首页 > news >正文

算法总结：图论——拓扑序

news 2026/4/25 21:46:07

线段树实在写不下去了，来写一下拓扑序吧。

模版参见某谷B3644
大意：给出每个人的后代的信息。输出一个序列，使得每个人的后辈都比那个人后列出。

思路

这玩意儿有点简单：
这个家族的关系很显然可以用有向图来表示。
假设边的方向是由祖先指向后辈，那么后辈一定会有入度。

在图论中，顶点的度(d e g r e e degreedegree)是指与该顶点相连的边的数量，指向该顶点的边数即为入度。

所以，每次只需要找到入度为0的点，将其加入答案中，并将其后辈的入度-1，如此循环即可。
数据结构上，可以用队列存入度为0的点。

代码

#include<bits/stdc++.h>usingnamespacestd;#defineN103intn,into[N];queue<int>q;vector<int>ans;vector<int>g[N];intmain(){cin>>n;for(inti=1;i<=n;i++){while(1){intx;cin>>x;if(x==0)break;g[i].push_back(x);into[x]++;}}for(inti=1;i<=n;i++)if(into[i]==0)q.push(i);while(!q.empty()){intu=q.front();q.pop();ans.push_back(u);for(intv:g[u]){into[v]--;if(into[v]==0)q.push(v);}}for(inta:ans)cout<<a<<" ";return0;}

小试牛刀：P4017

_{题外话：一看到生物想到自己地生会考的成绩就闹心ε=(´ο｀*)))}

题目大意就是找食物网中最大食物链(即从生产者到最高级消费者)的数量。

思路

~~很显然~~是DP(万物皆可DP)。
状态：d p [ u ] dp[u]dp[u]表示强制以u uu结尾的食物链的条数。
根据生物知识，食物链的方向由低到高。如果u uu的捕食者是v vv，那么所有指向u uu的食物链都会指向v vv。
将食物网建成有向图，拓扑排序后v vv就一定在u uu的后面。
转移：在拓扑排序的基础上，对于所有入度为0的点向外拓展，并将自己的d p dpdp值加到它的捕食者上。
答案：将所有出度为0(最高级消费者)的点的d p dpdp值相加即可。
初始化：将所有入度为0(生产者)的点初始化为1，其余为0。

代码

#include<bits/stdc++.h>usingnamespacestd;#defineN5001#definemod80112002intn,m,dp[N],into[N],out[N];vector<int>g[N];queue<int>q;intmain(){cin>>n>>m;for(inti=1;i<=m;i++){intu,v;cin>>u>>v;g[u].push_back(v);into[v]++;out[u]++;}for(inti=1;i<=n;i++){if(into[i]==0){dp[i]=1;q.push(i);}}while(!q.empty()){intu=q.front();q.pop();for(intv:g[u]){into[v]--;if(into[v]==0)q.push(v);dp[v]=(dp[v]+dp[u])%mod;}}intans=0;for(inti=1;i<=n;i++)if(out[i]==0)ans=(ans+dp[i])%mod;cout<<ans;return0;}