先可以将所有出度为0的节点连向一个点，然后问题变为求到这个点的必经之点
这其实是一道模板题，因为有一个东西叫做支配树
容易发现一个点的必经之点都是一条链，其实可以把这条链上最浅的点作为这个点的父亲，那么一个点的所有必经之点显然就是他到根的路径上的点
具体来说，这个点的父亲就是他所有联通的点的lca（不能叫lca，可以用拓扑来求）
最终支配树上所询问两个点的lca深度就是答案
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 100005 4 queue<int>q; 5 vector<int>a[N],b[N]; 6 int n,m,x,y,vis[N],sh[N],f[N][21]; 7 int lca(int x,int y){ 8 if (sh[x]<sh[y])swap(x,y); 9 for(int i=20;i>=0;i--) 10 if (sh[x]-(1<<i)>=sh[y])x=f[x][i]; 11 if (x==y)return x; 12 for(int i=20;i>=0;i--) 13 if (f[x][i]!=f[y][i]){ 14 x=f[x][i]; 15 y=f[y][i]; 16 } 17 return f[x][0]; 18 } 19 int main(){ 20 scanf("%d%d",&n,&m); 21 for(int i=1;i<=m;i++){ 22 scanf("%d%d",&x,&y); 23 a[x].push_back(y); 24 b[y].push_back(x); 25 vis[x]++; 26 } 27 for(int i=1;i<=n;i++) 28 if (!vis[i])q.push(i); 29 while (!q.empty()){ 30 int k=q.front(); 31 q.pop(); 32 int v=0; 33 if (a[k].size()){ 34 v=a[k][0]; 35 for(int i=1;i<a[k].size();i++)v=lca(v,a[k][i]); 36 } 37 sh[k]=sh[v]+1; 38 f[k][0]=v; 39 for(int i=1;i<=20;i++)f[k][i]=f[f[k][i-1]][i-1]; 40 for(int i=0;i<b[k].size();i++) 41 if (--vis[b[k][i]]==0)q.push(b[k][i]); 42 } 43 scanf("%d",&m); 44 for(int i=1;i<=m;i++){ 45 scanf("%d%d",&x,&y); 46 printf("%d ",sh[lca(x,y)]); 47 } 48 }