E. Monsters

Problem - 1810E - Codeforces

思路：我们总结一下题意，能够得到这个题其实就是让我们从某个0开始搜索，然后看看是否可以遍历所有得节点，那么如果采用暴力得话那就是n^2logn，因为我们遍历一次使用优先队列得话是nlogn的，但是通过总结我们发现了一个性质，每个点被遍历的次数不超过logn次，因为假设在我们现在正在遍历以u开始的点，那么假设在某一次遍历中遍历到了一个节点t，这个节点已经在以v开始的节点中被遍历过了，那么如果我现在能够遍历到节点t，那么就代表我可以遍历所有v能够遍历到的点，那么现在的数量起码就是cnt[v]*2，那么我们知道了，每次重复遍历一个节点，那么能够遍历到的点就会乘以2，那么每个点最多只会被遍历logn次

// Problem: E. Monsters
// Contest: Codeforces - CodeTON Round 4 (Div. 1 + Div. 2, Rated, Prizes!)
// URL: https://codeforces.com/problemset/problem/1810/E?mobile=false
// Memory Limit: 256 MB
// Time Limit: 2000 ms
 
#include
#include
#include
#define fi first
#define se second
#define i128 __int128
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> PII;
const double eps=1e-7;
const int N=5e5+7 ,M=5e5+7, INF=0x3f3f3f3f,mod=1e9+7,mod1=998244353;
const long long int llINF=0x3f3f3f3f3f3f3f3f;
inline ll read() {ll x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') {x=(ll)x*10+c-'0';c=getchar();} return x*f;}
inline void write(ll x) {if(x < 0) {putchar('-'); x = -x;}if(x >= 10) write(x / 10);putchar(x % 10 + '0');}
inline void write(ll x,char ch) {write(x);putchar(ch);}
void stin() {freopen("in_put.txt","r",stdin);freopen("my_out_put.txt","w",stdout);}
bool cmp0(int a,int b) {return a>b;}
template<typename T> T gcd(T a,T b) {return b==0?a:gcd(b,a%b);}
template<typename T> T lcm(T a,T b) {return a*b/gcd(a,b);}
void hack() {printf("\n----------------------------------\n");}
 
int T,hackT;
int n,m,k;
int cost[N];
int h[N],e[M],ne[M],idx;
bool st[N];
int stt[N];
 
void add(int a,int b) {
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
 
bool bfs(int u) {
	priority_queue,greater > q;
	q.push({cost[u],u});
	
	int res=0;
	while(q.size()) {
		auto it=q.top();
		q.pop();
		
		int ver=it.se;
		if(it.fi>res) break;
		
		if(stt[ver]==u) continue;
		st[ver]=true;
		stt[ver]=u;
		res++;
		
		for(int i=h[ver];i!=-1;i=ne[i]) {
			int j=e[i];
			
			q.push({cost[j],j});
		}
	}
	
	return res==n;
}
 
void solve() {
	n=read(),m=read();
	
	memset(st,false,sizeof(bool)*(n+4));
	memset(stt,0,sizeof(int)*(n+4));
	for(int i=1;i<=n;i++) cost[i]=read();
	
	memset(h,-1,sizeof(int)*(n+4));
	idx=0;
	while(m--) {
		int a=read(),b=read();
		add(a,b),add(b,a);
	}
	
	bool flag=false;
	for(int i=1;i<=n;i++) {
		if(st[i]) continue;
		if(cost[i]!=0) continue;
		if(bfs(i)) {
			flag=true;
		}
	}
	
	if(flag) printf("YES\n");
	else printf("NO\n");
}   
 
int main() {
    // init();
    // stin();
	// ios::sync_with_stdio(false); 
 
    scanf("%d",&T);
    // T=1; 
    while(T--) hackT++,solve();
    
    return 0;       
}