拓扑排序
拓扑排序就是将图的每个点进行排序,以入度为0 为起点,进行沿着图进行排序输出
再讲拓扑排序之前,要讲两个概念入度和出度
-
啥是入度
就是一个点的有点多少个指向它的边(这里不能有重边) -
啥是出度
就是一个点有多少个它指向其他点的边(这里不能有重边)
拓扑排序的怎样写
1 记录入度和出度的多少
2 将入度为0的点装进队列
3 每次遍历点,将该点的入度减一,为0加入队列
其实具体问题还是要具体分析,但思维还是没什么差别
来一道具体问题
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=1e6+10;
int h[N],e[M],ne[M],idx; //邻接表
int d[N],r[N],c[N];
int n,m,ans;
inline int read() { //快读
char c = getchar(); int n = 0;
while (c < '0' || c > '9') { c = getchar(); }
while (c >= '0' && c <= '9') { n = (n << 1) + (n << 3) + (c & 15); c = getchar(); }
return n;
}
void add(int a,int b){ //存边
e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
void spfa(){
queue<int> q;
for(int i=1;i<=n;i++)
if(r[i]==0){
q.push(i); //入度为零,加入队列作为起点
d[i]=1;
}
while(q.size()){
int t=q.front();
q.pop();
for(int i=h[t];~i;i=ne[i]){
int j=e[i];
d[j]+=d[t]; //记录该点以有多少条食物链
r[j]--; //每次入度减一
if(!r[j]){ //入度为零加入队列
if(c[j]) q.push(j); //出度不为0,即不为终点,加入队列
else ans+=d[j]; //出度为零为终点,此时加食物链的个数
}
}
}
}
int main(){
cin>>n>>m;
memset(h,-1,sizeof h); //邻接表初始化
for(;m;m--){
int a,b;
a=read(),b=read();
add(a,b); //食物链不存在重边
c[a]++; //入度和出度记录
r[b]++;
}
spfa();
cout<<ans; //输出
return 0;
}