杭電2019多校第三場 HDU-6604 Blow up the city（支配樹+必經點個數）

連結：http://acm.hdu.edu.cn/showproblem.php?pid=6604

題意：T組樣例。第一行給出n、m（n個點，m條單向邊）。接下來m行描述這條邊（給出u、v）u->v。再給一個q，表明q個詢問，每個詢問給出a、b。詢問有多少點，那它去掉後，a、b中至少一個點不能到達出度為0的點。（也就是a或b到達所有出度為0的點的必經點的個數，在反向圖中也就是所有入度為0的點到a或b的必經點的個數。）。題目說了該圖是一個DAG。

思路：一個圖是DAG的話，求必經點的個數就簡單多了。我們逆向思考，如果我們建反向圖，并且把反向圖中入度為0的點（也就是原圖中出度為0的點）和一個超級源點0（即支配樹中的根節點）相連，那麼這個有可能為森林的圖，就變成了一棵樹。這棵樹就是我們需要的支配樹。那麼一個詢問（a、b）的答案，就轉化為求a、b的必經點的個數。由支配樹的性質，一個點的必經點的個數就是其在支配樹上到根節點的距離，那麼答案就是deep[a]+deep[b]-deep[Lca(a,b)]。是以這個題，我們不必把支配樹建出來，隻需要記下支配樹中每個點的深度和倍增找LCA所需要的資訊即可。（具體參考https://blog.csdn.net/birdmanqin/article/details/97816603  很類似）

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+10;
int deep[N],f[N][20],in[N],id[N],q[N],he,ta;
int n,m,root,num,u,v,Q;
vector<int> g[N];
void Init()
{
	memset(f,0,sizeof(f));
	for(int i=0;i<=n;i++)
		in[i]=0,g[i].clear();
	return ;	
} 
void TopoSort()
{	
	//把根節點的深度設為0，友善計算 
	deep[root]=0;
	//根節點的父親還是根節點 
	f[root][0]=root; 
	num=0;
	he=ta=0;
 	for(int i=1;i<=n;i++)
 		if(!in[i])	q[ta++]=i;	
	while(he!=ta)
	{
		u=q[he++];
		//記下每個拓撲序的點 
		id[++num]=u;
		for(int i=0;i<g[u].size();i++)
		{
			v=g[u][i];
			in[v]--;
			if(!in[v])
			{
				q[ta++]=v;
			}
		}
	}
	return;
}
//倍增求LCA 
int Lca(int x,int y)
{
	if(deep[x]<deep[y])
		swap(x,y);
	int diff=deep[x]-deep[y];
	for(int i=0;i<=17;i++)//從小往大找 
		if(diff&(1<<i)) x=f[x][i];
	if(x==y) return x;
	for(int i=17;i>=0;i--)
		if(f[x][i]!=f[y][i])
			x=f[x][i],y=f[y][i];
	return f[x][0];
}
int main(void)
{
	//cout<<(1<<17)<<endl;
	root=0;
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		Init();
		//說反向圖是為了好了解還是正向建圖，
		//因為後面要用到已經與其相連并且在支配樹的點的LCA
		//來确定每個點在支配樹中的父親。 
		 
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d",&u,&v);
			g[u].push_back(v);
			in[v]++;	
		}	
		TopoSort();
		//拓撲排序倒序建支配樹 
		for(int i=n;i>=1;i--)
		{	
			v=id[i];
			//也就是出度為0的點，直接與根節點0相連 
			if(!g[v].size())
			{
				f[v][0]=root;
				deep[v]=deep[root]+1;
				continue;
			}
			u=g[v][0]; 
			for(int j=1;j<g[v].size();j++)
				u=Lca(u,g[v][j]);
			deep[v]=deep[u]+1;
			f[v][0]=u;
			for(int i=1;i<=17;i++)
				f[v][i]=f[f[v][i-1]][i-1];
		}
		scanf("%d",&Q);
		while(Q--)
		{
			scanf("%d%d",&u,&v);
			//因為我的根節點的深度為0，算出來剛好是答案 
			printf("%d\n",deep[u]+deep[v]-deep[Lca(u,v)]);			
		}		
	}
	
	return 0;
}