C++(g++ 7.5.0) 解法, 执行用时: 79ms, 内存消耗: 16196K, 提交时间: 2022-12-02 20:42:47

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int i,j,k,n,m,t,f[2005][2005],g[2005],res;

void dfs(int x){
	//printf("NMSL%d %d\n",x,g[x]);
	for(int i=1;i<=n;i++){
		if(!f[x][i])continue;
		if(~g[i]){
			if(g[i]==g[x]){
				res=1;return;
			}
			continue;
		}
		g[i]=1-g[x];dfs(i);
	}
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>t;
	while(t--){
		cin>>n>>m;
		if(n>=2000){
			for(i=1;i<=m;i++)cin>>j>>k;
			cout<<"YES\n";continue;
		}
		memset(f,1,sizeof(f));
		memset(g,-1,sizeof(g));
		for(i=1;i<=n;i++)f[i][i]=0;
		for(i=1;i<=m;i++){
			cin>>j>>k;
			f[j][k]=f[k][j]=0;
		}
		res=0;
		for(i=1;i<=n;i++){
			if(g[i]==-1){
				g[i]=0;dfs(i);
			}
			if(res)break;
		}
		if(res)cout<<"YES\n";
		else cout<<"NO\n";
	}
}

C++(clang++ 11.0.1) 解法, 执行用时: 78ms, 内存消耗: 10728K, 提交时间: 2022-12-02 20:05:59

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N=2e5+10;
bool sb=0;
int vis[N];
vector<int> e[N];
int a=0,b=0;
void dfs(int x){
	vis[x]=1;
	b++;a+=e[x].size();
	for(auto v:e[x]){
		if(!vis[v]) dfs(v);
	}
}
void solve(){
	sb=0;
	int cnt=0;
	int n,m;cin>>n>>m;
	for(int i=1;i<=n;i++) vis[i]=0,e[i].clear();
	for(int i=1;i<=m;i++){
		int x,y;cin>>x>>y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			a=0;b=0;
			dfs(i);
			cnt++;
			if(a!=b*(b-1)) sb=1;
		}
	}
//	cout<<cnt<<" "<<sb<<endl;
	if(cnt==2&&!sb) cout<<"NO"<<endl;
	else cout<<"YES"<<endl;
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int T=1;
	cin>>T;
	while(T--) solve();
	return 0;
}