洛谷 P4017 -> Click Here

题意

一个 DAG（又向无环图），询问从无入度的点到无出度的点的路径个数有多少个

思路

拓扑排序

找出无出度的点加入到队列中，更新与当前点有边的点，删去此点及其边，再寻找新的无入度的点加入到队列中

code

#include<iostream>
#include<map>
#include<queue>
#define REP(i,a,b) for(int i=(a);i<=(b);i++)
using namespace std;
const int MOD = 80112002;//从原题上复制下来，格式有错没看见，狂WA不过（裂开
struct edge{
	int nxt;
	int to;
}G[500005];//链式前向星 这里数组大小为边的数目，不是点的（WA死我了
int head[50005],cnt;
int n,m,ans;
map<int,int> mp,chu;
queue<int> q;
int A[50005];
void Add(int a,int b){
	cnt++;
	G[cnt].nxt=head[a];
	head[a]=cnt;
	G[cnt].to=b;
}
int main(){
	cin>>n>>m;
	for(int i=1,a,b;i<=m;i++){
		cin>>a>>b;
		chu[a]++;
		mp[b]++;
		Add(a,b);
	}
	for(int i=1;i<=n;i++){
		if(mp[i]==0) {q.push(i);A[i]=1;}
	}
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=G[i].nxt){
			int u=G[i].to;
			A[u]=(A[u]+A[x])%MOD;
			mp[u]--;
			if(mp[u]==0){
				q.push(u);
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(chu[i]==0){
			ans=(ans+A[i])%MOD;
		}
	}
	cout<<ans<<endl;
}