记录编号	222661	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	DAGCH	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	4.380 s
提交时间	2016-02-03 21:07:18	内存使用	4.61 MiB

#include<cstdio>
#include<vector>
#include<iostream>
#include<cstring>
using namespace std;
const int SIZEN=100010;
vector<int> s[SIZEN],c[SIZEN];
int N,M,Q;
void read()
{
	scanf("%d%d%d",&N,&M,&Q);
	for(int i=1;i<=N;i++) s[i].clear(),c[i].clear();
	int v,u;
	for(int i=1;i<=M;i++)
	{
		scanf("%d%d",&u,&v);
		s[u].push_back(v);
		c[v].push_back(u);
	}
}
int fa[SIZEN],sdom[SIZEN],mi[SIZEN],ufs[SIZEN];
bool vis[SIZEN];
int timer;
void dfs(int x)
{
	vis[x]=0;
	timer++;
	for(int i=0;i<s[x].size();i++)
	{
		int u=s[x][i];
		if(!vis[u]&&u==timer+1) fa[u]=x,dfs(u);
	}
}
int find(int x)
{
	if(x==ufs[x]) return x;
	int y=find(ufs[x]);
	if(sdom[mi[ufs[x]]]<sdom[mi[x]]) mi[x]=mi[ufs[x]];
	return ufs[x]=y;
}
void lengauer_tarjan()
{
	for(int i=1;i<=N;i++) ufs[i]=mi[i]=sdom[i]=i;
	for(int i=N;i>=1;i--)
	{
		for(int j=0;j<c[i].size();j++)
		{
			int u=c[i][j];
			find(u);
			//cout<<i<<" "<<u<<" "<<mi[u]<<endl;
			sdom[i]=min(sdom[i],sdom[mi[u]]);
		}
		ufs[i]=fa[i];
	}
}
int ans[SIZEN];
void work()
{
	memset(vis,0,sizeof(vis));
	fa[1]=0;
	timer=0;
	dfs(1);
	//for(int i=1;i<=N;i++) cout<<fa[i]<<" ";
	//cout<<endl;
	lengauer_tarjan();
	memset(ans,0,sizeof(ans));
	for(int i=2;i<=N;i++) ans[sdom[i]]++;
	int A;
	for(int i=1;i<=Q;i++)
	{
		scanf("%d",&A);
		printf("%d ",ans[A]);
	}
	printf("\n");
}
int T;
int main()
{
	freopen("dagch.in","r",stdin);
	freopen("dagch.out","w",stdout);
	scanf("%d",&T);
	while(T>0)
	{
		T--;
		read();
		//cout<<T<<endl;
		work();
	}
	return 0;
}