A.牛妹的游戏（拉姆塞理论）

A.牛妹的游戏（拉姆塞理论）

题目传送门

题意：给一无向无权图 n个点，m条边，问是否有长度为3的环或者3个点都互相不相连。

思路：当n>=6时，必定存在3个点互相相连或者互相不相连。当n<6时暴力即可。

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
#define mst(a) memset(a,0,sizeof a)
#define jg(i,j,k) (a[i][j]&&a[i][k]&&a[j][k]||(!a[i][j]&&!a[j][k]&&!a[i][k]))
int main(){
	int t;
    scanf("%d",&t);
    while(t--){
        int n,m,x,y,a[6][6],f=0;
        scanf("%d%d",&n,&m);
        if(n>5){
            while(m--)
            scanf("%d%d",&x,&y);
        }
        else {
             while(m--)
            scanf("%d%d",&x,&y),a[x][y]=a[y][x]=1;
        }
        if(n>5) puts("yes");
        else {
            for(int i=1;i<=n-2;i++)
               for(int j=i+1;j<=n-1;j++)
                   for(int k=j+1;k<=n;k++)
                       if(jg(i,j,k))
                       {
                           f=1;
                           break;
                       }
             puts(f?"yes":"no");
        }
    }
	return 0;
}