个人网站开发总结文档,html网页作业,lnmpa wordpress,wordpress 功能插件正题 大意
一个图有n个点#xff0c;每次增加一条边。每次增加一条边之后统计每个点度数大于0且是偶数的子图个数。 解题思路
首先满足要求的子图至少有一个环#xff0c;然后我们考虑每加入一个环和别的环的判断情况。每加入一个环的话我们会发现其实就是有若干个环之中选…正题 大意
一个图有n个点每次增加一条边。每次增加一条边之后统计每个点度数大于0且是偶数的子图个数。 解题思路
首先满足要求的子图至少有一个环然后我们考虑每加入一个环和别的环的判断情况。每加入一个环的话我们会发现其实就是有若干个环之中选择一些我们可以用一个01串来表示是否选择这个环那么这个01串的全排列就是答案当然要计算上只选一个环的情况。 用并查集判断环如果发现一个新环就统计ans不然就连接。 代码
#includecstdio
using namespace std;
int n,m,father[200001],ans,x,y;
int find(int x)
{if (father[x]x) return x;return father[x]find(father[x]);
}
int main()
{scanf(%d%d,n,m);for (int i1;in;i)father[i]i;for (int i1;im;i){scanf(%d%d,x,y);if (find(x)!find(y)){int fafind(x),fbfind(y);//连接if (fafb) father[fa]fb;else father[fb]fa;}else ans(ans*21)%1000000009;//统计答案printf(%d\n,ans);}
}
