2019 蓝桥杯国赛 B 组模拟赛 E 蒜头图 （并查集判环）

思路：

我们看条件，发现满足条件的子图无非就是一些环构成的图，

因为只有形成环，才满足边的两个点都在子图中，并且子图中节点的度是大于0的偶数。

那么如果当前有k个环，我们可以选2^k-1个子图，为什么？

我们从这k个环中选择 1~n个都可以满足条件，那么就是C(k,1)+C(k,2)+C(k,3)+...+C(k,n) = 2^k-1

接下来就看如何判定当前图有多少个环？

我们每加一个边，如果加入之前，这个边的两个端点ａ，ｂ，如果a和b已经在图中联通了，那么加上这条边必多一个子图为环。

我们用并查集来维护两个节点是否联通即可。

细节见代码：

#include<bits/stdc++.h>
using namespace std;

const int mod = 1046513837;
int n,m,f[200500];

int find(int x){
    return f[x] == x ? x : f[x] = find(f[x]);
}

void merge(int a,int b){
    int x = find(a);
    int y = find(b);
    if(x != y ) f[x] = y;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) f[i] = i;
    long long ans = 1;
    for(int i=1 ;i<=m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        int x = find(a), y = find(b);
        if(x == y){//这里如果 两个点祖先一样 说明找到环了
            ans <<= 1;
            if(ans > mod) ans -= mod;
        }else merge(a,b);
        printf("%lld
",ans-1);
    }
    return 0;
}