博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Codeforces 91C Ski Base 加边求欧拉回路数量
阅读量:7099 次
发布时间:2019-06-28

本文共 2384 字,大约阅读时间需要 7 分钟。

题目链接:

题意:

给出n个点m条无向边的图

開始图里没有边。每次加一条边,然后输出图里欧拉回路的条数。

思路:

We will count the number of ski bases including the base consisted of empty subset of edges (before printing just subtract one). In the beginning the number of bases is equal to 1. If we connect vertexes in the same connected components then the result should be multiplied by 2 else do nothing. You should use DJS data structure to know information about connected components where vertexes are and to unite them.

Why is it correct?

To prove it we will use the matrix of incidence I, rows in it will be edges and columns will be vertexes. Let's define xor of two rows. Xor of two rows a и b will be row c such that ci = ai xor bi. Notice if  xor of some subset of rows is equal to a zero row then this subset form the ski base. It's correct because, the degree of contiguity of every vertex is even, so we can form an Euler cycle in every connected component. The answer is  2(m - rank(I))
Why it is correct? Let's write the number of edge from the right of each row which suit this row. While finding the matrix rank using gauss method with xor operation, we will xor the subsets from the right of the strings. In the end the subsets of edges written from the right of the zero rows will form the basis of the linear space. Thats why we can take any subset of vectors from basis and make up a new ski base. The number of these subsets is equal to 2k = 2(m - rank(I)), where k is the number of zero rows.

The last thing we should notice that the adding row is liner depended if and only if there is exist a way between the vertexes a and b (aand b are the ends of the adding edge).

#include 
#include
#include
#include
#include
#include
#include
using namespace std;const int N = 100100; const int mod = 1000000009;int f[N];int find(int x){ return x == f[x] ?

x : f[x] = find(f[x]); } bool Union(int x, int y){ int fx = find(x), fy = find(y); if (fx == fy)return false; if (fx > fy)swap(fx, fy); f[fx] = fy; return true; } int n, m; int main(){ while (cin >> n >> m){ for (int i = 1; i <= n; i++)f[i] = i; int ans = 1; while (m--){ int u, v; scanf("%d %d", &u, &v); if (Union(u, v)==false) ans = (ans + ans) % mod; printf("%d\n", ans-1); } } return 0; }

转载于:https://www.cnblogs.com/yutingliuyl/p/6856493.html

你可能感兴趣的文章
我的友情链接
查看>>
Linux IO和管道练习题
查看>>
2048游戏完整源代码揭秘和下载 (一)
查看>>
gitlab项目数据同步
查看>>
关于Service与Broadcast以及Notification的终于告一段落了
查看>>
VO,PO,POJO的定义和区别
查看>>
Python环境搭建
查看>>
瑞信CDP与HA集群
查看>>
RAID各级别的特性
查看>>
Python学习笔记__7.3章 多重继承
查看>>
爱创课堂每日一题七十天- 说说你对前端架构师的理解?
查看>>
兄弟连第7节课
查看>>
学习笔记(11月15日)
查看>>
JavaWeb21-HTML篇笔记
查看>>
Java之品优购部署_day03(3)
查看>>
前端与移动开发之vue-day4(2)
查看>>
phpcms筛选功能
查看>>
简练软考知识点整理-制定进度计划过程
查看>>
26 LAMP
查看>>
Oracle解决用户锁的问题
查看>>