水库选址

题目链接：ybt 入门到进阶模拟赛 Day2 T1

题目大意

给你一些点的高度，水可以从高的传到地的，同样高度不行。
然后又一些点直接相邻，代表可以传水。
要你在一个地方建水库，使得所有点都有水。
如果可以，就输出 Yes 和建的地方，否则输出 No。

思路

容易想到肯定是选最高的那个做水库。
那如果有多个最高直接 No。

然后就不断的找新的有水的地点往外流。
然后最后判断一下是不是全部点都有谁就可以了。

代码

#include<queue>
#include<cstdio>
#define ll long long

using namespace std;

struct node {
	int to, nxt;
}e[1001];
int n, m, num, le[1001], KK, x, y;
ll ans, a[301], X;
bool in[301], same;
queue <int> q;

void add(int x, int y) {
	e[++KK] = (node){y, le[x]}; le[x] = KK;
	e[++KK] = (node){x, le[y]}; le[y] = KK;
}

int main() {
//	freopen("water.in", "r", stdin);
//	freopen("water.out", "w", stdout);
	
	ans = -1e15;
	
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
		if (a[i] > ans) {
			ans = a[i];
			X = i;
			same = 0;
		}
		else if (a[i] == ans) {
			same = 1;
		}
	}
	
	for (int i = 1; i <= m; i++) {
		scanf("%d %d", &x, &y);
		add(x, y);
	}
	
	if (same) {//最高的有两个或以上，一定不行
		printf("No");
		return 0;
	}
	
	q.push(X);
	in[X] = 1;
	num = 1; 
	while (!q.empty()) {
		int now = q.front();//按顺序枚举每个新有水的点流水
		q.pop();
		
		for (int i = le[now]; i; i = e[i].nxt)
			if (!in[e[i].to] && a[now] > a[e[i].to]) {
				in[e[i].to] = 1;
				q.push(e[i].to);
				num++;
				if (num == n) {//所有点都有水了
					printf("Yes\n%d", X);//输出的是最高那个的编号
					return 0;
				}
			}
	}
	
	if (num == n) {
		printf("Yes\n%d", X);
		return 0;
	}
	
	printf("No");
	
	return 0;
}