看完题面，我马上趁教练不注意 打开了某399小游戏。熟练地找到了这个。颓废了一上午 就想到怎么做了。

对于一个灯和所以与他相连的等灯。每个灯只有按和不按两种情况。为什么呢？ 如果同一盏灯按了两次。就跟没按时一样的。三次亦是如此。由此可得，按奇数次的效果等于按了一次，按偶数次等于没按。

确定了这个关系，我们就可以使用位运算，异或进行列方程了。

啥？方程？等等，smg？

我们要求的是每个灯是否被按。

这就是我们的未知数。

我们设计一下系数，如果一盏灯对于其他的灯有影响，那么这盏灯所对应的未知数在被影响的灯的方程中就是一。如果某一盏灯对其他灯没有影响，他的系数就是0.（0异或任何数都是原数，对答案不产生影响）。

又由于异或具有交换律和结合律。所以可以用来移项。

---

而题目中是所问的是最少关多少盏灯灯全部打开所有灯。

这就提示我们，有很大可能会出现自由元（就是可以任意取值的未知数）

然后我们来看数据范围。

\(ok\)

位置数个数小于等于35.

枚举全部状态肯定不行。

不过如果只枚举自由元，再加上最优性剪枝，应该是可以跑过去的。

233

然后我是stl毒瘤选手。

怎么能不用bitset呢

#include
    
      #include
     
      #include
      
       #include
       
        using namespace std;bitset<38>g[38];int n,m;void gauss(){    for(int i=1;i<=n;i++)    {        int r=i;        for(int j=i+1;j<=n;j++)            if(g[j][i])            {                r=j;                break;            }        if(r!=i)            swap(g[i],g[r]);        for(int j=i+1;j<=n;j++)            if(g[j][i])                g[j]^=g[i];//bitset可以整体异或    }}int ans=0x7fffffff;int base[38];void dfs(int now,int sum)//就是回带，now就是回带到多少个了（n~1），sum为当前开的灯的数量{    if(sum>ans)        return ;    if(now==0)    {        ans=min(ans,sum);        return ;    }    if(g[now][now])    {        base[now]=g[now][n+1];        for(int i=now+1;i<=n;i++)            base[now]^=(base[i]&g[now][i]);//要乘系数。这里利用了与运算进行加速（为什么可以，可以自行枚举判断真确性）        if(base[now])//如果这个灯是开的            dfs(now-1,sum+1);        else            dfs(now-1,sum);    }    else//自由元    {        base[now]=0;        dfs(now-1,sum);        base[now]=1;        dfs(now-1,sum+1);//枚举一波    }}int main(){    scanf("%d%d",&n,&m);    int a,b;    for(int i=1;i<=n;i++)        g[i][n+1]=g[i][i]=1;    for(int i=1;i<=m;i++)    {        scanf("%d%d",&a,&b);        g[a][b]=1;        g[b][a]=1;    }    gauss();    dfs(n,0);    printf("%d",ans);}