思路：大佬博客-https://www.cnblogs.com/fisherss/p/10857705.html#idx_4
看完觉得有道理，但还是不太明白orz
实际上就是问图里有多少个环，计环的个数为 k，则结果为2^k-1。 30% 状态压缩选出边，判断所选的边是否构成环 100% 并查集统计环的数量，使用并查集每次询问只需要判断这两点之前是否连通就可以了，为什么结果是2^k-1呢(k表示环的数量)，有大佬说了：题目表明了“只要构成蒜头图就算一种情况”，那么也就是说从原图中取1个环也能构成环，取其中两个环也能构成环(有环就代表是蒜头图的子图，管你取几个环都是蒜头图).......C(n,i) i从1~k都能构成环 那么C(n,1) + C(n,2) + C(n,3) + C(n,k)就是答案，这个式子的值也等于2^k ，最后还要-1
Code:
#include<iostream> using namespace std; typedef long long LL; const int MAX_N=1e5+5; const LL MOD=1046513837; int n,m; int id[MAX_N]; int Find(int x){ if(id[x]!=x) id[x]=Find(id[x]); return id[x]; } void Union(int a,int b){ id[Find(a)]=Find(b); } int main() { ios::sync_with_stdio(false); cin>>n>>m; for(int i=0;i<=n;++i) id[i]=i; LL ans=1; int u,v; while(m--){ cin>>u>>v; if(Find(u)==Find(v)) ans=(ans*2)%MOD; else Union(u,v); cout<<(ans-1+MOD)%MOD<<endl; } return 0; }
