牛妹的游戏

UPD:数据保证不会有两条控制链控制的据点完全相同，也保证不会有某条控制链两端控制的据点相同。

牛妹最近沉迷于一个名为 ingress 的游戏中...

游戏中，蓝绿营两个对立阵营互相角力，通过争夺据点来控制区域。

具体来说，二维的平面上分布有若干据点，玩家可以通过XM扫描器来控制这些据点。
同一阵营控制的两个据点可以相连成为一条被该阵营控制的链。
而同一阵营控制的三条链，首尾相接可以形成一块被该阵营控制的区域。

如下图为一块被蓝方控制的区域：

但是这样的游戏没有一个胜利或失败结局，牛牛觉得很不舒服，于是他开发出了 imgress。

这个游戏和 ingress 的区别在于，如果一个阵营控制了一块区域，则形成这块区域的据点无法再被另一阵营控制。

此外，imgress 的玩家并非直接对据点进行控制，而是通过在据点间形成控制链来间接控制对应据点，于是可能出现同一个据点被两方的控制链所使用的情况。

现在，牛妹加入了蓝方阵营，她已经得知了场上的总据点数，和蓝方已经形成的所有控制链。

现在她想知道目前场上是否可能已经存在被玩家控制的区域，你需要帮她解决这个问题。

第一行一个正整数 T，表示数据组数。

每组数据的第一行有两个正整数 n 和 m，表示场上总据点数为 n，此时蓝方已经形成了 m 条控制链。

接下来 m 行，每行有两个正整数 x 和 y，表示这条控制链由据点 x 和据点 y 形成。

#include<bits/stdc++.h> using namespace std; const int N=5e4+10; long long t,n,m,x,y,der[N],sum; void init(){ memset(der,0,sizeof der); sum=0; } int main(){ for(cin>>t;t--;){ cin>>n>>m; init(); for(int i=0;i<m;i++){ cin>>x>>y; der[x]++, der[y]++; } for(int i=1;i<=n;i++) sum+=(n-1-der[i])*der[i]; sum>>=1; if(n*(n-1)*(n-2)/6-sum>0) puts("yes"); else puts("no"); } return 0; }

#include<bits/stdc++.h> using namespace std; const int N=50010; int t[N]; int T,n,m; int main(){ scanf("%d",&T); while(T--){ scanf("%d %d",&n,&m); for(int i=1;i<=n;i++) t[i]=0; int x,y; for(int i=1;i<=m;i++){ scanf("%d %d",&x,&y); t[x]++;t[y]++; } long long tot=0; for(int i=1;i<=n;i++) tot+=1ll*(n-t[i]-1)*t[i];tot/=2; printf(1ll*n*(n-1)*(n-2)/6-tot>0?"yes\n":"no\n"); } }

详情