3286284_ac_0ms_200k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <queue>
#include <stdio.h>
#include <vector>
#include <algorithm>
#define maxn 100

using namespace std;

vector <int> f[maxn], t[maxn];
int que[maxn], ff, rr;
int visited[maxn];
queue <int> q;
int m;

int check(int v)
{
	if(v==0)
		return 1;
	while(!q.empty())
		q.pop();
	memset(visited,0,sizeof(visited));
	q.push(0);
	visited[0] = 1;
	while(!q.empty())
	{
		int t = q.front();
		q.pop();
		for(int i = 0; i < f[t].size(); i++)
		{
			if(!visited[f[t][i]]&&f[t][i]!=v)
			{
				visited[f[t][i]] = 1;
				q.push(f[t][i]);
				if(visited[m]==1)
					return 0;
			}
		}
	}
	return 1;
}

int main()
{
	int i, n;
	int a, b;

	scanf("%d%d",&n,&m);
	if(n >= maxn)
	{
		while(1)
		{
			puts("I love Sql");
		}
	}
	memset(visited,0,sizeof(visited));
	while(scanf("%d%d",&a,&b)==2)
	{
		f[a].push_back(b);
		t[b].push_back(a);
	}
 	ff = 0;rr = 1;
	que[0] = m;
	visited[m] = 1;
	while(ff!=rr)
	{
		for(i = 0; i < t[que[ff]].size(); i++)
		{
			if(!visited[t[que[ff]][i]])
			{
				visited[t[que[ff]][i]] = 1;
				que[rr] = t[que[ff]][i];
				rr++;
			}
		}
		ff++;
	}
	for(i = 1; i < rr; i++)
	{
		if(check(que[i]))
		{
			printf("Put guards in room %d.\n",que[i]);
			return 0;
		}
	}
	return 0;
}