提交时间:2025-11-26 21:15:40
运行 ID: 38986
#include<bits/stdc++.h> using namespace std; #define N 1145 int n,m,p[N]; bitset<N>a[N]; int faCnt[N]; bool in[N][N]; bool vis[N]; void solve(){ cin>>n>>m; memset(vis,0,sizeof(vis)); memset(in,0,sizeof(in)); memset(faCnt,0,sizeof(faCnt)); for(int i=1;i<=n;i++) a[i].reset(); for(int i=1,j;i<=m;i++){ cin>>p[i]; for(int k=1;k<=p[i];k++){ cin>>j; a[j][i]=1; } } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(i==j) continue; if((a[i]|a[j])==a[j]){ // cout<<i<<' '<<j<<' '<<a[i].to_string()<<' '<<a[j].to_string()<<endl; in[i][j]=1; faCnt[i]++; } } } for(int stp=1;stp<n;stp++){ int son=0,fa; for(int i=1;i<=n;i++){ if(vis[i] || !faCnt[i]) continue; for(int j=1;j<=n;j++){ if(i==j || vis[j]) continue; if(in[i][j]){ son=i,fa=j; break; } } if(son) break; } if(!son){ cout<<"NO"<<endl; return; } // cout<<son<<' '<<fa<<endl; vis[son]=1; for(int i=1;i<=n;i++){ if(i==fa || vis[i]) continue; if(in[i][son]){ in[i][son]=0; faCnt[i]--; } } for(int i=1;i<=m;i++){ a[son][i]=0; p[i]--; if(p[i]==1){ a[fa][i]=0; p[i]=0; } } for(int i=1;i<=n;i++){ if(i==fa || vis[i]) continue; if((a[fa]|a[i])==a[i]){ in[fa][i]=1; faCnt[fa]++; } } } cout<<"YES"<<endl; } int main(){ ios::sync_with_stdio(0); int t; cin>>t; while(t--) solve(); return 0; }