點(diǎn)這里

結(jié)論題😅 ，圖一樂

結(jié)論：如果原圖中存在兩個邊集不交的生成樹，那么$\text{Bob}$必勝；否則$\text{Alice}$必勝

證明有點(diǎn)難😅

首先，考慮維護(hù)兩顆 不存在紅邊 的生成樹，如果$\text{Alice}$斷掉了其中一顆樹上的一條邊，將這個樹分成兩個連通塊，那么$\text{Bob}$一定可以在另一顆樹上選擇一條邊變成藍(lán)色，使得這個樹再次聯(lián)通，最終兩個生成樹都只由藍(lán)邊構(gòu)成

其次，如果原圖中不存在這樣的兩顆生成樹，則考慮某次$\text{Alice}$操作時，$\text{Bob}$勝利的條件：將所有藍(lán)色的邊 復(fù)制一遍，使得存在兩個邊集不交的生成樹。假設(shè)存在某種策略，使得$\text{Bob}$在某次操作后滿足了這個條件，那么$\text{Alice}$可以照搬$\text{Bob}$的策略，使得某次操作后將紅邊復(fù)制一遍，使得存在兩個邊集不交的生成樹。因此$\text{Alice}$存在可以讓紅邊構(gòu)成一顆生成樹的策略。又因?yàn)樵瓐D中不存在兩個邊集不交的生成樹，因此$\text{Bob}$無法勝利

有點(diǎn)絞

發(fā)現(xiàn)$\left(\genfrac{}{}{0ex}{}{30}{9}\right)$比較小，直接暴搜即可。

#include<cstdio>
#include<iostream>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define db double
#define ull unsigned long long
#define inf 0x3f3f3f3f
using namespace std;
int n,m,fa[10],fa2[10],U[30],V[30],s[30];
int find(int x){return fa[x]==x?x:find(fa[x]);
}
int check(){for(int i=0;i<n;i++)fa2[i]=fa[i],fa[i]=i;int tot=0;for(int i=0;i<m;i++){if(s[i]==0){int x=find(U[i]),y=find(V[i]);if(x!=y)fa[x]=y,tot++;}}if(tot==n-1){return 1;}for(int i=0;i<n;i++)fa[i]=fa2[i];return 0;
}
int dfs(int x,int y){if(y==n-1)return check();for(int i=x;i<m;i++){int a=find(U[i]),b=find(V[i]);if(a==b)continue;fa[a]=b,s[i]=1;if(dfs(i+1,y+1))return 1;fa[a]=a,s[i]=0;}return 0;
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);while(cin>>n>>m){if(n==-1&&m==-1)break;for(int i=0;i<n;i++)fa[i]=i;for(int i=0;i<m;i++)cin>>U[i]>>V[i],s[i]=0;cout<<(dfs(0,0)?"YES":"NO")<<"\n";}
}