nkoj1851——Get Tools from Doraemon's Pocket

拓扑排序+BFS.

#include<stdio.h>
#include<string.h>
int n,m,edge;
#define max 10005
struct node
{
	int u,v;
}tt[max*100];
int marry[max],queue[max],vis[max],v[max],dgree[max];
int find(int t)
{
	int i,front=0,rear=0,sum=1;
	queue[++rear]=t;
	while(front!=rear)
	{
		int k=queue[++front];
		for(i=0;i<edge;i++)
			if(tt[i].v==k&&vis[tt[i].u])
			{
				queue[++rear]=tt[i].u;
				sum++;
				vis[tt[i].u]=false;
			}
	}
	return sum;
}
void PFTP()
{
	int i,j,k,front=0,rear=0,t;
	memset(dgree,0,sizeof(dgree));
	memset(vis,true,sizeof(vis));
	memset(v,true,sizeof(v));
	for(i=0;i<edge;i++)
	{
		dgree[tt[i].v]++;
	}
	for(i=1;i<=n;i++)
		if(dgree[i]==0)
		{
			queue[++rear]=i;
			vis[i]=false;
		}
	while(front!=rear)
	{
		t=queue[++front];
		v[t]=false;
		for(i=0;i<edge;i++)
		{
			if(tt[i].u==t&&vis[tt[i].v])
			{
				dgree[tt[i].v]--;
			}
		}
		for(i=1;i<=n;i++)
		{
			if(dgree[i]==0&&vis[i])
			{
				queue[++rear]=i;
				vis[i]=false;
			}
		}
	}
	int sumn=0,sumstep=0;
	memset(vis,true,sizeof(vis));
	for(i=0;i<m;i++)
	{
		t=marry[i];
		if(v[t]==false)
		{
			sumn++;
			if(vis[t])
			{vis[t]=false;sumstep+=find(t);}
		}
	}
	printf("%d %d\n",sumn,sumstep);
}
int main()
{
	int i,a,b,j,k;
	edge=0;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&k);
		for(j=0;j<k;j++)
		{
			scanf("%d",&a);
			tt[edge].u=a;tt[edge].v=i;
			edge++;
		}
	}
	scanf("%d",&m);
	for(i=0;i<m;i++)
		scanf("%d",&marry[i]);
	PFTP();
	return 0;
}