图的拓扑排序
图论的拓扑排序
前提有向图、无环、图忽略方向后是连通的（没有孤立点和孤立边）
拓扑排序的目标是将所有节点排序，使得排在前面的节点不能依赖于排在后面的节点
来自 https://oi-wiki.org/graph/topo/
由于入度相同的节点可能有多个，所以拓扑排序顺序不唯一，但按字典序排序后唯一
思路如下：
需要一个队列
先找出入度为0的节点，全部入队
然后开始循环（队列非空）：
1.取出队首，记录出队顺序
2.队头节点相连的所有节点(队头节点出去的节点）的入度-=1
若此时某个节点入度为0就入队
反复循环直到队列空停止
为什么正确呢？
因为先找出入度为0的节点
然后把相连的节点入度减一，当入度为0时入队相当于按顺序遍历有向图
而队列满足先进先出，所以出队顺序就是拓扑序
为什么这里不用vis判重?
当图无环时，当前入度为0的点所相连的点不可能再能到达当前点，因为当前点入度为0了
所以一个节点只入队一次，不需要判重
当图有环时，可能某个当前入度为0的点指向的下一个节点在环中，但由于环使得环中每一个节点入度均不为0，所以
环中任何节点入度不可能为0，所以环中节点不会被入队，所以不会造成重复，不需要判重
怎么
判断环
呢？
第一种用拓扑本身，记录出队序列时记录下出队的个数
如果出队的个数==节点数则无环
如果出队的个数<节点数则有环（因为有环就会使得环中节点不入队，出队个数少了）
采用队列法求拓扑邻接矩阵\(O(n^2 )\)
采用队列法求拓扑邻接表\(O(n+m)\)
\(n\)是点数\(m\)是边数（\(n\)个点出队，一共遍历\(m\)条边找相连点）
采用队列法求拓扑邻接表要求字典序最小用优先队列\(O(nlogn+m)\)
（\(n\)个点出队\(O(n)\),排序需要\(logn\))
也可以用
dfs+栈
来拓扑：
先从一个入度为0的节点开始，递归搜索所有相连的节点，并且设立访问标志vis【i】，vis【i】=-1为正在访问该节点，vis【i】=1为已经访问过该节点，vis【i】=0为未访问该节点
如果在对一个节点访问前该节点已经为-1说明又回到了这个节点，说明图有环，停止dfs
然后dfs所有未访问过的节点，进行访问，一定要在访问完成后再对该节点设立vis为1！！因为如果在访问前对该节点设为访问标志1的话那么访问时-1会覆盖标志1，导致一直认为该节点在访问。
执行完遍历相连边的操作后再把当前节点入栈
完成一个操作后再遍历其它入度为0的节点，这样出栈顺序就是拓扑序
用栈因为栈后进先出，出度为0的节点在后面
入度为0的点在前面，所以无需逆序输出
Dfs邻接表时间\(O（n+m)\),空间\(O（v)\)(不考虑答案数组)
队列法未判断环的邻接表拓扑：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
struct edge{
int dis, to;
edge(int dis,int to=0):dis(dis),to(to){
}
};
using namespace std;
inline void solve(int n,int m){
vector<edge>g[105];
int indeg[105];
queue<int>q;
memset(indeg,0,sizeof indeg);
for(int i=0;i<m;++i){
int a,b;
cin>>a>>b;
g[a].push_back(edge(1,b));
++indeg[b];
}
for(int i=1;i<=n;++i){
if(indeg[i]==0)q.push(i);
}
while(!q.empty()){
int k=q.front();
q.pop();
cout<<k<<" ";
for(int i=0;i<g[k].size();++i){
int tos=g[k][i].to;
--indeg[tos];
if(indeg[tos]==0)q.push(tos);
}
}
}
int main(){
int n,m;
while((cin>>n>>m)&&!(!n&&!m)){
solve(n,m);
cout<<endl;
}
return 0;
}
取自
www.luogu.com.cn/problem/UVA10305
dfs版拓扑（邻接表已判断环）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<stack>
using namespace std;
stack<int>ans;
int indeg[105],vis[105];
inline int dfs(int k,vector<int>g[105]){
vis[k]=-1;
for(int i=0;i<g[k].size();++i){
int& tos=g[k][i];
if(vis[tos]==-1)return false;
if(!vis[tos]){
dfs(tos,g);
}
}
vis[k]=1;
ans.push(k);
return true;
}
inline void solve(int n,int m){
// while(!ans.empty())ans.pop();
vector<int>g[105];
memset(indeg,0,sizeof indeg);
memset(vis,0,sizeof vis);
for(int i=0;i<m;++i){
int a,b;
cin>>a>>b;
g[a].push_back(b);
++indeg[b];
}
for(int i=1;i<=n;++i){
if(indeg[i]==0){
// cout<<9;
if(!dfs(i,g))return ;
vis[i]=1;
}
}
while(!ans.empty()){
cout<<ans.top()<<" ";
ans.pop();
}
}
int main(){
int n,m;
while((cin>>n>>m)&&!(!n&&!m)){
solve(n,m);//不要再读入n和m了！！
cout<<endl;
}
return 0;
}
例题
Luogu4017
https://www.luogu.com.cn/problem/P4017 题面
最大食物链计数
把问题抽象成图论问题
因为满足生物学要求，不会出现环，所以图没有重边和自环，且是有向图
生物就是图的节点，从\(a\)到\(b\)连一条边代表\(a\)被\(b\)吃
所以变成了图论问题
生产者为入度为\(0\)的节点，最高级消费者为出度为\(0\)的节点
相当于求有多少条路径能从任意一个入度为\(0\)到任意一个出度为\(0\)的节点
这种问数量的题一般用递推
若设\(f(i)\)点以\(i\)为终点的食物链条数
则\(f(i)=\)所有指向\(i\)的节点的食物链条数之和
可以用记忆化搜索，逆向搜索，搜索以\(i\)为起点的食物链条数，当点出度为\(0\)时返回\(1\)
也可以用拓扑正向搜索，将入度为\(0\)的节点食物链条数设为\(1\)，不需要先生成拓扑序列再递推，这样同层节点不好处理，应该在拓扑排序遍历节点减少入度时将该节点相连的节点的食物链条数\(+=\)该节点的食物链条数（加法原理）
输出所有出度为\(0\)节点食物链条数即可
但要注意孤立点不算食物链，要减去
一个孤立点的入度和出度均为\(0\)，可以借此判断，然后总和减去孤立点的个数
注意不能直接调用入度\(indeg\)数组，因为拓扑时入度已经修改了，所以统计入度时再开一个备份数组\(indeg1[]\)，用它来判断孤立点
别忘了分步取模
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
const int mod=(1ll<<31);
struct edge{
int to;
edge(int to):to(to){
}
};
vector<edge>g[100006];
int num[100006],indeg[100006],outdeg[100006],indeg1[100006];
int main(){
int n,m;
cin>>n>>m;
memset(num,0,sizeof num);
memset(indeg,0,sizeof indeg);
memset(indeg1,0,sizeof indeg1);
memset(outdeg,0,sizeof outdeg);
for(int i=0;i<m;++i){
int a,b;
cin>>a>>b;
g[a].push_back(edge(b));
++indeg[b] ;
++indeg1[b] ;//备份indeg数组
++outdeg[a];
}
queue<int>q;
for(int i=1;i<=n;++i){
if(indeg[i]==0){
q.push(i);
num[i]=1;
}
}
while(!q.empty() ){
int k=q.front() ;
q.pop() ;
for(int i=0;i<g[k].size() ;++i){
int tos=g[k][i].to;
--indeg[tos];
num[tos]=(num[tos]%mod+num[k]%mod)%mod;//递推
if(indeg[tos]==0){
q.push(tos);
}
}
}
int sum=0;
for(int i=1;i<=n;++i){
if(indeg1[i]==0&&outdeg[i]==0)sum=(sum-1)%mod;//孤立点判断
if(outdeg[i]==0){
sum=(sum%mod+num[i]%mod)%mod;
}
}
cout<<sum%mod<<endl;
return 0;
}
Luogu1983车站分级
题面 https://www.luogu.com.cn/problem/P1983
题目上说如果一个车站停靠，那么所有等级大于等于该停靠站的都要停靠，所以凡是非停靠站的等级一定小于所有停靠站的等级
即对于每一个停靠站\(x\)，非停靠站的级别一定小于\(x\)的级别
所以可以转化成图论问题
\(n\)个车站可以看成节点，每一个车次的每个非停靠站向，每个停靠站连一条有向边，代表非停靠站等级小于停靠站等级，对于每个车次的起点和终点也算停靠站，所以每个车次的第一个停靠站和最后一个停靠站决定这个车的起点和终点，在这个范围内进行连边，由于题目说满足要求，所以不存在环
此时入度为\(0\)的节点时非停靠站，等级最低，出度为\(0\)的节点一定为停靠站，等级最高
要求至少的等级数相当于要求每一条入度为\(0\)到出度为\(0\)的路径中经过节点最多的那个路径的经过的点数，因为经过多的路径分级多，能够满足所有需求
所以要先建图，然后进行拓扑排序，注意建立图时从一个节点到另一个节点的边只能建立一次，要判重防止重边
拓扑排序时递推，设\(f(x)\)为以\(x\)为终点的所经过最大的点数，则\(f(x)=\)所有指向\(x\)的节点的经过的最大点数的最大值\(+1\)
利用拓扑递推，然后遍历所有出度为\(0\)的节点的\(f（x）\)，找出最大值，即为分级数
m个读入车次
每次从停靠点向非停靠点连边需要\(N^2\),所以建图\(O(n^2 * m)\)，拓扑\(O(n^2 * m +n)\),最终为\(O(n^2 * m)\)，但是由于避免重边且每次停靠点不足\(n\)个，所以实际效率较高
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define re register
using namespace std;
struct edge{
int to;
edge(int to):to(to){
}
};
vector<edge>g[1006];
int num[1006],a[1006],hash[1006],indeg[1006],outdeg[1006],vis[1006][1006];
int main(){
memset(hash,0,sizeof hash);
memset(indeg,0,sizeof indeg);
memset(outdeg,0,sizeof outdeg);
memset(vis,0,sizeof vis);
int n,m;
scanf("%d%d",&n,&m);
for(re int i=0;i<m;++i){
int s;
scanf("%d",&s);
int la,st;
scanf("%d",&a[0]);
la=st=a[0];//实际起点并不总是1点，要看第一个停靠站，实际终点要看最后一个停靠站
hash[a[0]]=1;
for(re int j=1;j<s;++j){
// int ni;
scanf("%d",&a[j]);
la=a[j];
hash[a[j]]=1;//停靠点标记
}
for(re int j=0;j<s;++j){
for(re int k=st;k<=la;++k){
if(hash[k]){
if(j==s-1)hash[k]=0;//多个车次hash需要清空，避免memset低效率，采用这种方法
continue;
}
if(!vis[k][a[j]]){//避免重边
vis[k][a[j]]=1;
g[k].push_back(edge(a[j])); //建图
++indeg[a[j]];
++outdeg[k];
}
}
}
}
// for(int i=1;i<=n;++i){
// if(indeg[i]==0){
// cout<<i<<" ";
// }
// }
queue<int>q;
for( int i=1;i<=n;++i){
if(indeg[i]==0){
num[i]=1;
q.push(i);
}
}
while(!q.empty() ){
int k=q.front() ;
q.pop() ;
for(re int i=0;i<g[k].size() ;++i){
int tos=g[k][i].to;
--indeg[tos];
num[tos]=max(num[tos],num[k]+1);//递推
if(indeg[tos]==0)q.push(tos);
}
}
int maxi=-1e6;
for(re int i=1;i<=n;++i){
if(outdeg[i]==0&&num[i]>maxi){//出度为0的等级最大值为答案
maxi=num[i];
}
}
cout<<maxi<<endl;
return 0;
}
黄粱一梦，终是一空
本文来自博客园，作者：hicode002，转载请注明原文链接：https://chuna2.787528.xyz/hicode002/p/19526582
浙公网安备 33010602011771号