ACM程序设计选修课——1081: 堆（BFS）

 

1081: 堆

Time Limit: 1 Sec   Memory Limit: 128 MB
Submit: 26   Solved: 9

Description

 

Input

 

Output

 

Sample Input

3
1
10
3
10 5 3
1 2
1 3
5
1 2 3 4 5
3 1
2 1
2 4
2 5

Sample Output

Yes
No
Yes

 

 

嗯好久之前的题了。由于自己树这方面不是很懂也没学过数据结构，然后就没敢做。趁着下午考六级早上随便找点题热热身= =没想到1A了，惊喜……

代码：

#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define INF 0x3f3f3f3f
#define MM(x) memset(x,0,sizeof(x))
#define MMINF(x) memset(x,INF,sizeof(x))
const double PI=acos(-1.0);
using namespace std;
typedef long long LL;
const int N=110;
vector<int>E[N];
int val[N];
int vis[N];
void init()
{
	MM(vis);
	MM(val);
	for (int i=0; i<N; i++)
		E[i].clear();
}
int main(void)
{
	int tcase,i,j,x,y,z,n;
	scanf("%d",&tcase);
	while (tcase--)
	{
		init();
		scanf("%d",&n);
		for (i=1; i<=n; i++)
		{
			scanf("%d",&val[i]);
		}
		for (i=1; i<=n-1; i++)
		{
			scanf("%d%d",&x,&y);
			E[x].push_back(y);
			E[y].push_back(x);
		}
		queue<int>Q;
		Q.push(1);
		set<int>pos;
		while (!Q.empty())
		{
			int now=Q.front();
			Q.pop();
			pos.insert(now);
			vis[now]=1;
			for (i=0; i<E[now].size(); i++)
			{
				int v=E[now][i];
				if(val[now]<=val[v]&&(!vis[v]))
				{
					Q.push(v);
				}
			}
		}
		if(pos.size()==n)
			puts("Yes");
		else
			puts("No");
	}
	return 0;
}