なるほど…。
https://yukicoder.me/problems/no/2900
問題
赤青の点からなる二部グラフが与えられる。
各辺は赤点と青点を結んでおり、また各点の次数は1以上である。
このうち、半分以上の点を含む部分誘導グラフで、含まれる青点と隣接する赤点が奇数となるものの一例を求めよ。
解法
乱択で部分誘導グラフに残す赤点を選ぶ。
あとは条件を満たす青点を残すと、そこそこの確率で条件を満たせるようだ。
int T; int X,Y,M; set<int> E[202020]; int okA[202020],okB[202020]; void solve() { int i,j,k,l,r,x,y; string s; cin>>T; while(T--) { cin>>X>>Y>>M; FOR(i,X+Y) E[i].clear(); FOR(i,M) { cin>>x>>y; E[x-1].insert(y-1); } int sa=0,sb=0; while(1) { sa=sb=0; FOR(i,Y) { okB[i]=(rand()<rand()); sb+=okB[i]; } FOR(i,X) { x=0; FORR(e,E[i]) x^=okB[e]; okA[i]=x; sa+=x; } if(sa+sb>=(X+Y+1)/2) break; } cout<<sa<<" "<<sb<<endl; FOR(i,X) if(okA[i]) cout<<i+1<<" "; cout<<endl; FOR(i,Y) if(okB[i]) cout<<i+1<<" "; cout<<endl; } }
まとめ
確率どのぐらいになるんだろうな。