[关闭]
@ysner 2018-08-05T20:13:17.000000Z 字数 1026 阅读 2169

黑魔法师之门

结论


题面

给出一个大小为的无向图,求图中每个点的度数大于零且都是偶数的子图的个数。

解析

子图不一定是联通的!!!
则设图中最小环(不由其它环组成的环)的个数为
如果同一联通块中的点再次联通,就构成了一个新的最小环。
因为这些环选与不选都可构成新子图,于是
(去掉一个环都不选的情况)。

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<algorithm>
  7. #include<vector>
  8. #define re register
  9. #define il inline
  10. #define ll long long
  11. #define max(a,b) ((a)>(b)?(a):(b))
  12. #define min(a,b) ((a)<(b)?(a):(b))
  13. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  14. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  15. using namespace std;
  16. const int mod=1e9+9,N=1e6+100;
  17. ll n,m,h[N],cnt,f[N],ans;
  18. il ll gi()
  19. {
  20. re ll x=0,t=1;
  21. re char ch=getchar();
  22. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  23. if(ch=='-') t=-1,ch=getchar();
  24. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  25. return x*t;
  26. }
  27. il int find(re int x){return x==f[x]?x:f[x]=find(f[x]);}
  28. int main()
  29. {
  30. freopen("magician.in","r",stdin);
  31. freopen("magician.out","w",stdout);
  32. n=gi();m=gi();
  33. fp(i,1,n) f[i]=i;
  34. fp(i,1,m)
  35. {
  36. re int u=gi(),v=gi(),fu=find(u),fv=find(v);
  37. if(fu^fv) f[fu]=fv;
  38. else ans=(ans*2+1)%mod;
  39. printf("%lld\n",ans);
  40. }
  41. fclose(stdin);
  42. fclose(stdout);
  43. return 0;
  44. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注