牛客练习赛62 A.牛妹的游戏

题目大意:给定n个点m无向边，求该图和图的补图是否有度数为3的环.
分析：
比赛时疯狂讨论边情况...wa自闭了
正确题解:

• 拉姆塞结论--点数超过5的图和对应补图必有度数为3的环.不会证明(只会举例子)
• 那么点数少于6的图直接暴力找环即可.

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

typedef long long ll;
const int maxn=20;
const int mod=998244353;


bool mp[maxn][maxn];

int main()
{
    int t;
    cin>>t;
    while( t-- )
    {
        int n,m;
        scanf("%d%d",&n,&m);
        memset(mp,false,sizeof(mp));
        if( n>5 )
        {
            for( int i=1;i<=m;i++ )
            {
                int x,y;scanf("%d%d",&x,&y);
            }
            puts("yes");
            continue;
        }

        for( int i=1;i<=m;i++ )
        {
            int x,y;scanf("%d%d",&x,&y);
            mp[x][y]=mp[y][x]=1;
        } 
        int flag=0;
        for( int i=1;i<=n;i++ )
        {
            for( int j=i+1;j<=n;j++ )
            {
                for( int k=j+1;k<=n;k++ )
                {
                    int c=mp[i][j]+mp[j][k]+mp[k][i];
                    if( c==0 || c==3 )    flag=1;
                }
            }
        }
        if( flag ) puts("yes");
        else puts("no");
    }
}