zoj1376.cpp

最近在acm.zju.edu.cn上通过的题目的代码

#include <stdio.h>
#include <memory.h>
#include <map>
#include <vector>

using namespace std;

int n,k;

vector <int> adj[110];
map<int,int> dict;
int st[110];

void input()
{
	scanf("%d %d",&n,&k);
	int i,id,j,x,m;
	dict.clear();
	for (i=0;i<n;++i)
	{
		scanf("%d %d",&id,&m);
		dict[id]=i;
		adj[i].clear();
		for (j=0;j<m;++j)
		{
			scanf("%d",&x);
			adj[i].push_back(x);
		}
	}
	for (i=0;i<n;++i)
		for (j=0;j<adj[i].size();++j)
			adj[i][j]=dict[adj[i][j]];
	for (i=0;i<k;++i)
		scanf("%d",st+i);
	for (i=0;i<k;++i)
		st[i]=dict[st[i]];
}

bool vst[110][110][3];
int	qx[1100],qt[1100];

void bfs(const int &rb)
{
	memset(vst[rb],0,sizeof(vst[rb]));
	qx[0]=st[rb];
	qt[0]=0;
	vst[rb][st[rb]][0]=1;
	int hd=0,tl=1,ax,at,bx,bt,i;
	while (hd<tl)
	{
		ax=qx[hd];
		at=qt[hd];
		bt=1-at;
		++hd;
		for (i=0;i<adj[ax].size();++i)
		{
			bx=adj[ax][i];
			if (!vst[rb][bx][bt])
			{
				vst[rb][bx][bt]=1;
				qx[tl]=bx;
				qt[tl]=bt;
				++tl;
			}
		}
	}
}

bool judge()
{
	int i,j,rb;
	bool flag;
	for (rb=0;rb<k;++rb)
		bfs(rb);
	for (i=0;i<n;++i)
		for (j=0;j<2;++j)
		{
			flag=1;
			for (rb=0;rb<k&&flag;++rb)
				if (!vst[rb][i][j]) flag=0;
			if (flag) return 1;
		}
	return 0;
}

int main()
{
	int cs;
	scanf("%d",&cs);
	while (cs--)
	{
		input();
		if (judge()) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}