DAG 求u到v路径数

sadlin / 2024-09-04 / 原文

DAG 求u到v的路径数

先拓扑排序求出每个点的顺序，再对每个起点 $s$ 做 dp，遍历拓扑序的点，对 $s$ 能到达的点做 dp 统计路径数，如果终点 $t$ 拓扑序在 $s$ 之前就说明没有路径。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 200005
const int mod=1e9+7;

int n,m,qq;

int cnt=0;
struct Edge{
	int to,next;
}edge[2*N];
int head[N];

void add_edge(int u,int v){
	cnt++;
	edge[cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt;
} 

int in[N];
queue<int> q;

vector<int> a;

void topo_sort(){
	
	for(int i=1;i<=n;i++){
		if(!in[i]){
			q.push(i);
		}
	}
	
	while(!q.empty()){
		int x=q.front();
		q.pop();
		a.push_back(x);
		
		for(int i=head[x];i!=-1;i=edge[i].next){
			int y=edge[i].to;
			
			if(--in[y]==0){
				q.push(y);
			}
		}
	}
}

int ans[N];

void dp(int s){
	
	for(int i=1;i<=n;i++){
		ans[i]=0;
	} 
	ans[s]=1;
	
	for(int i=0;i<a.size();i++){
		int x=a[i];
		
		if(ans[x]>0){//起点 s 能到这个点 
			for(int j=head[x];j!=-1;j=edge[j].next){
				ans[edge[j].to]+=ans[x];
				ans[edge[j].to]%=mod;	
			}
		}
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m>>qq;
	
	for(int i=1;i<=n;i++){
		head[i]=-1;
	} 
	
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		add_edge(u,v);
		in[v]++;
	}
	
	topo_sort();
	
	for(int i=1;i<=qq;i++){
		int s,t;
		cin>>s>>t;
		
		dp(s);
		
		cout<<ans[t]<<"\n";	
	}
	return 0; 
}