鏈接：

時間限制：C/C++ 1秒，其他語言2秒 空間限制：C/C++ 262144K，其他語言524288K 64bit IO Format: %lld

題目描述

UPD:數據保證不會有兩條控制鏈控制的據點完全相同，也保證不會有某條控制鏈兩端控制的據點相同。

牛妹最近沉迷于一個名為 ingress 的游戲中…

游戲中，藍綠營兩個對立陣營互相角力，通過爭奪據點來控制區域。 具體來說，二維的平面上分布有若干據點，玩家可以通過XM掃描器來控制這些據點。
同一陣營控制的兩個據點可以相連成為一條被該陣營控制的鏈。 而同一陣營控制的三條鏈，首尾相接可以形成一塊被該陣營控制的區域。
如下圖為一塊被藍方控制的區域：

但是這樣的游戲沒有一個勝利或失敗結局，牛牛覺得很不舒服，于是他開發出了 imgress。 這個游戲和 ingress
的區別在于，如果一個陣營控制了一塊區域，則形成這塊區域的據點無法再被另一陣營控制。 此外，imgress
的玩家并非直接對據點進行控制，而是通過在據點間形成控制鏈來間接控制對應據點，于是可能出現同一個據點被兩方的控制鏈所使用的情況。

現在，牛妹加入了藍方陣營，她已經得知了場上的總據點數，和藍方已經形成的所有控制鏈。
現在她想知道目前場上是否可能已經存在被玩家控制的區域，你需要幫她解決這個問題。

輸入描述:

第一行一個正整數 T，表示數據組數。 每組數據的第一行有兩個正整數 n 和 m，表示場上總據點數為 n，此時藍方已經形成了 m 條控制鏈。
接下來 m 行，每行有兩個正整數 x 和 y，表示這條控制鏈由據點 x 和據點 y 形成。

輸出描述:

對于每組數據，如果目前場上有可能存在被玩家控制的區域，則輸出一行 “yes”，否則輸出一行 “no”。（均不包含引號）

示例1
輸入

2 3 3 1 2 2 3 3 1 5 5 1 2 2 3 3 4 4 5 5 1

輸出

yes no

說明

對于第一組數據，藍方在所有據點間形成了控制鏈，此時的情況如下圖所示：

可以發現藍方已經形成了控制區域。

對于第二組數據，藍方的 5 條控制鏈首尾相接，如下圖所示：

此時藍方沒有形成控制區域，同時，可以發現綠方即使控制了所有藍方沒有控制的鏈，也無法形成控制區域。

題意：

我來把題目濃縮下：就是給你一個無向圖，問這個圖和它的補圖是否存在三元環？
如果圖本身有三元環就是藍方贏，如補圖有三元環，就是綠方贏，但題目是問你藍綠方有一方能贏就輸出yes，都不能就輸出no

題解：

有一個結論：如果點>=6的話，它以及它的補圖一定存在三元環。
網上說這個叫拉姆塞結論（我們離散也沒講過 ）
點數小于6的話，暴力就OK了，先標記給的邊，三層for循環，看看任意三個邊能不能構成環。

代碼：

#include<bits/stdc++.h> #define mem(a) memset(a,0,sizeof(a)) using namespace std; const int mod = 1e9 + 7; const int maxn=102; int n,sum; int f[102][102]; void biaoji(int x,int y) {f[x][y]=1;f[y][x]=1; } int main() {int T,n,m,a,b;cin>>T;while(T--){sum=0;mem(f);cin>>n>>m;for(int i=1;i<=m;i++){cin>>a>>b;biaoji(a,b);}if(n>=6){cout<<"yes"; }else{for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)for(int k=j+1;k<=n;k++){int w=f[i][j]+f[j][k]+f[k][i];if(w==0||w==3)sum++;if(sum)break;}if(sum)cout<<"yes"<<endl;else cout<<"no"<<endl;}} }

總結

以上是生活随笔為你收集整理的牛妹的游戏的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。