day3上午——图论

正睿青岛

一个无向图有偶数个度数为奇数的点。

havel-hakimi算法:

问是否存在简单图的点的度数序列是 给定的序列
将度数序列从大到小排序，$d_1, d_2...d_n$，每次考虑最大的，它连向除去d1的前d1大的点，将它们减1，继续判断第二个。（贪心）
简单图：无自环，重边的无向图

E

要求对于任意的1<=k<=n的k，都要满足：
$\sum_i^k d_i \leq k\times(k-1) + \sum_{i=k+1}^nmin(d_i)$
前面表示前k个点的所有的度数，它们能连的最大的度数。
后面：k*(K-1)表示k个点内可以两两相连，min(d_i)表示能往后面k个点连的最大的度数。

valid CF1037D

给一个bfs序列，一棵树，判断能否bfs这棵树，得到这个序列。
将邻接表中的点

dfs forset

有向图：树边，前向边，返祖边，横插边
无向图：树边，前向边，反祖边。
没有横插边。
假设有横插边，

HDU

判断有没有奇环，偶环。
奇环：判是不是二分图。
偶环：两种情况：
1、返祖边可以构成的环的存在偶环。
2、两个奇环去掉相交的可以构成偶环。
第二个：将所有的奇环的边都打上标记，就是起点位置打+1，终点打-1。找有没有重复的。

bitset

稠密图，可以直接存01矩阵，bitset优化。
bitset adj[N], notvis[N];
每个点可以访问的点就是 adj & notvis
每次找到第一个1。
找右边第一个1：lowbit(x)
lowbit得到的数是2的幂，而不是位数，找到位数：（好像有函数），打出2^0~2^16的表，p[8] = 3,p[1024]=10，然后如果小于2^16就直接得到，否则，就是右移16位，然后在找。

CF

环的交，就是两个环的交点。

欧拉回路

存在一条路径：每条边走过一次，回到起点。
如果有孤立点，那么就不管了，因为欧拉回路判断的是边，不需要图联通。
存在的充要条件：每个点的度数偶数，（所以出的等于进的）。
（如果每个点的度数都是偶数，从一个点出发，一定可以回来：停下的条件是这个点的度数为1（奇数），而只有终点是满足这个条件的）。
第一次访问后，第二次在访问这个点的时候，第一次访问的边不需要在访问了，类似dinic的方法，记录当前到那条边。
求欧拉序列：
每次从一个点出发，走到一个点的时候，如果无路可走，弹出，加入队列，然后回溯，在走还能走的点，不能走弹出，加入队列。
复杂度O(n+m)

bool vis[maxE]; 
void dfs(int x) {
    for (int &i=it[x]; i; i=nxt[i]) {
        if (!vis[to[i]]) {
            vis[i] = 1; // 无向边：En = 1, vis[i^1] = 1; 
            dfs(to[i]);
        }
    }
    q[qn++] = x;
}

CF 574 D Mike and fish

将行与列建点，如果有在这一行一列的，就是连边。将奇数点两两配对，连边，都变成偶数点，然后欧拉回路。走过的点一个红，一个蓝。去掉配对的边，刚好是满足这个点的红蓝相差小于等于1。

bzoj 3033 太鼓达人

生成一个2^n的01串，然后使每个长度为n的串都出现过。
建2^n的点，然后每个点表示长度为n的串，两个串之间有n-1的共同部分，这个点走到的点就是去掉0/1，加上一个0/1，构成的n个0/1的串。
但是这是求哈密顿回路，不太行。
那么每个点表示长度为n-1的串，每个点出去的两条边分别是0/1，然后去掉第一个加上这个0/1到达的串的点。那么每条边和之前的点，刚好构成所有的长度为n的串，所以直接走完所有的边，就是求欧拉回路。

最小生成树

prim / kruskal
n^2 / mlogm

Borůvka算法

算法
曼哈顿距离最大生成树
CF 异或最大生成树

最小瓶颈生成树

类似 nth_element O(n) 工作原理；
随机一个边权w，小于的加入，如果联通了，那么答案小于等于w，否则，就是大于w（大于的时候，缩点）。
T(m) = T(m/2) + O(m)。

CERC 16 Hanger Hurdles

n*n的网格图，每个点可能是障碍，求出从起点到终点的最大的可以通过的箱子。以起点为中心。
首先处理出每个点能通过的最的箱子，然后就是求一个路径，使最小值最大。求出最大生成树，倍增即可。

zjoixiantu

prufer序列

教程
求prufer序列：每次将所有的叶子节点中，选一个编号最小的，将它的父节点写入到prufer序列中，判断删除这个叶子节点后，父节点如果也成为了叶子，就加入到优先队列中。
转树：从未出现过的点中找到编号最小的，然后和第一个连边。删去第一个，如果第一个数也未出现了，加入到优先队列中。

生成树计数

完全图的生成树为n^(n-2)