题目描述：

n个点，m条边，每加一条边，问当前图中有多少个不同的环。

解题报告：

直接上结论：

用并查集维护

如果加边的两点已经是联通的，ans = (ans * 2 + 1) % mod

否则并查集相连即可。

代码如下；
#include<iostream>

#include<cstring>

#include<vector>

#include<algorithm>

#include<cmath>

#include<cstdio>

using namespace std;

#define SIZE 100005

#define mod 1000000009

int fa[SIZE], ans;

int find(int id)

{

    if (fa[id] == -1) return id;

    return fa[id] = find(fa[id]);

}

void un(int a, int b)

{

    int aa = find(a), bb = find(b);

    if (aa == bb) ans = (ans * 2 + 1) % mod;

    else fa[aa] = bb;

}

int main()

{

    int n, m;scanf("%d%d", &n, &m); ans = 0;

    memset(fa, -1, sizeof(fa));

    while(m--)

    {

        int a, b;scanf("%d%d", &a, &b);

        un(a, b);

        printf("%d\n", ans);

    }

         return 0;

}