AC日记——黑魔法师之门 codevs 1995

#include <cstdio>

#define maxn 200001
#define maxm 300000
#define mod 1000000009

using namespace std;

class Finding {
    private:
        int n,m,f[maxn],if_z;
        
        long long int ans;
        
        char Cget;
        
        inline void read_int(int &now)
        {
            now=0,if_z=1,Cget=getchar();
            while(Cget>‘9‘||Cget<‘0‘)
            {
                if(Cget==‘-‘) if_z=-1;
                Cget=getchar();
            }
            while(Cget>=‘0‘&&Cget<=‘9‘)
            {
                now=now*10+Cget-‘0‘;
                Cget=getchar();
            }
            now*=if_z;
        }
        
    public:
        Finding()
        {
            read_int(n),read_int(m);
            for(int i=1;i<=n;i++) f[i]=i;
            int x,y;
            for(int i=1;i<=m;i++)
            {
                read_int(x),read_int(y);
                x=Find(x),y=Find(y);
                if(x==y) ans=ans<<1|1;
                else f[x]=y;
                ans%=mod;
                printf("%lld\n",ans);
            }
        }
        
        int Find(int x)
        {
            if(f[x]==x) return x;
            f[x]=Find(f[x]);
            return f[x];
        }
};
class Finding do_;

int main()
{
    return 0;
}