提出 #56893050

---

ソースコード 拡げる

#include<bits/stdc++.h>
#ifdef xay5421
#define D(...) fprintf(stderr,__VA_ARGS__)
#define DD(...) D(#__VA_ARGS__ "="),debug_helper::debug(__VA_ARGS__),D("\n")
#include"/home/xay5421/debug.hpp"
#else
#define D(...) ((void)0)
#define DD(...) ((void)0)
#endif
#define pb push_back
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define each(x,v) for(auto&x:v)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
template<class T>void rd(T&x){int f=0,c;while(!isdigit(c=getchar()))f^=!(c^45);x=(c&15);while(isdigit(c=getchar()))x=x*10+(c&15);if(f)x=-x;}
template<class T>void pt(T x,int c=-1){if(x<0)putchar('-'),x=-x;if(x>9)pt(x/10);putchar(x%10+48);if(c!=-1)putchar(c);}
using namespace std;
using LL=long long;
using ULL=unsigned long long;
const int N=100005,M=1000005;
int T,n,m;
set<int>e[N];
int col[N];
int main(){
#ifdef xay5421
	freopen("a.in","r",stdin);
#endif
	rd(T);
	rep(tc,1,T){
		rd(n),rd(m);
		rep(i,1,n)e[i].clear();
		rep(i,1,m){
			int u,v;
			rd(u),rd(v);
			e[u].insert(v),e[v].insert(u);
		}
		set<int>S;
		rep(i,1,n)S.insert(i);
		rep(u,1,n)col[u]=-1;
		rep(s,1,n){
			if(col[s]!=-1){
				continue;
			}
			col[s]=0;
			queue<int>que;
			que.push(s);
			while(!que.empty()){
				int u=que.front();
				que.pop();
				set<int>nS;
				for(auto&x:S){
					if(e[u].count(x)){
						nS.insert(x);
					}else{
						col[x]=col[u]^1;
						que.push(x);
					}
				}
				S=move(nS);
			}
		}
		int c[2]={0,0};
		rep(i,1,n){
			++c[col[i]];
		}
		int es[2]={0,0};
		rep(u,1,n)for(auto&x:e[u])if(u<x&&col[u]==col[x])++es[col[u]];
		bool err=0;
		rep(o,0,1){
			if(1LL*c[o]*(c[o]-1)/2!=es[o])err=1;
		}
		puts(err?"No":"Yes");
	}
	return 0;
}

提出情報

ジャッジ結果