@图论个人总结二-个人总结
判链直接用度数，不要DFS判，会爆栈
以DFS序建立线段树维护时，线段树每个点的初值为num[ys[l]]
其中不是dfn[l]
一个点也能够成哈密顿回路
网络流记得建反边
写SPFA最好只用STL的queue，不要手写队列，因为不知道会入队几次，数组大小不好掌握
一棵树上与一个点距离为k的点不一定是它的祖先或子孙，可能是兄弟（有LCA）
差分约束
典型题1：给定一个序列，知道一些区间的和，判断是否合法；（P2294 [HNOI2005]狡猾的商人）；
建立前缀和差分约束系统，限制相等的条件是建立双向边；
有解的条件是不存在负环；
任意竞赛图（有向完全图）都存在哈密顿路径
求解欧拉（回）路
void efs(int x)
{
for(ri i = 0; i < to[x].size(); ++i)
if(!vis[to[x][i].se >> 1])
{
vis[to[x][i].se >> 1] = 1;
efs(to[x][i].fi);
}
ans[n--]=x;
}vector内存的是
一定要开栈之后倒序输出；
XOR路径/无向图上期望+高斯消元
自环不能加两次！自环不能加两次！自环不能加两次！
因为自环是一条边，加两次相当于这个点多了1条边；
临值查找
给定一个序列A，对于每个位置p，求在位置p前的，p对应的数的前驱和后继；
STL set 水过
但是有一个很好的思路：
先将A序列排序得到B序列，同时记录对应关系（A序列中的每个数在B序列中的位置）；
对B序列建立一个链表，记录前驱和后继；按A序列从后往前考虑，显然我们可以得到最后一个数的答案，然后，在链表中删除最后一个数，继续考虑下一个数；
最短路树
[SDOI2009]Elaxia的路线：求无向图中，两对点间最短路的最长公共路径
从四个端点出发跑一边最短路，于是我们就能确定有哪些点、边在x1,y1的最短路上；这些边构成了一个有向无环图，也就是最短路树；我们可以在拓扑序上DP，求出正向/反向的最短路长度；
用BFS求DFS序
锻炼思维的好题。
简单的说就是对于每个点，依次分配他的子树的DFS序，核心就是这一行：
for(ri i = head[x]; i; i = nx[i])
if(v[i] != fa[x][0])
{
dfn[v[i]] = use + 1;
use += sz[v[i]];
}为此，我们需要先BFS求出每个点的fa，再倒着按照BFS序，求出每个子树的sz，再正着bfs，求出dfn；
void bfs()
{
q[hd = tl = 1] = 1;
dep[1] = 1;
while(hd <= tl)
{
int x = q[hd++];
for(ri i = head[x]; i; i = nx[i])
if(v[i] != fa[x][0])
{
fa[v[i]][0] = x;
dep[v[i]] = dep[x] + 1;
q[++tl] = v[i];
}
}
for(ri i = n; i >= 1; --i)
{
++sz[q[i]];
sz[fa[q[i]][0]] += sz[q[i]];
}
dfn[1] = 1;
for(ri i = 1; i <= n; ++i)
{
int x = q[i], use = dfn[x];
ys[dfn[x]] = x;
for(ri i = 1; i <= 18; ++i)
{
fa[x][i] = fa[fa[x][i - 1]][i - 1];
if(fa[x][i] == 0) break;
}
for(ri i = head[x]; i; i = nx[i])
if(v[i] != fa[x][0])
{
dfn[v[i]] = use + 1;
use += sz[v[i]];
}
}
for(ri i = n; i >= 1; --i)
{
int mx = dfn[q[i]];
for(ri j = head[q[i]]; j; j = nx[j])
if(v[j] != fa[q[i]][0])
mx = max(out[v[j]], mx);
out[q[i]] = mx;
}
}P3119 [USACO15JAN]草鉴定
给定一张有向图，求从1号点回到1号点，可以重复经过点，至多可以反向走一条边，最多能到达多少点；
Tarjan缩点后两种方法：
法一：拓扑排序
我们考虑两种点：
<1> 以 1 为起点可以直接到达的，我们这里叫它一类点；
<2> 以该点为起点，可以直接到达 1 的，我们这里叫它二类点；拓扑排序预处理后，枚举从二类点到一类点的边，反着走这条边，更新答案；
注意对于1号点，特判一下；
法二：分层图SPFA
考虑一张图，将这个图复制一份，点的编号从1~N到(N+1)~(N+N)。然后在两层图中连边。对于原图上的每一条边，从原图的指向点到新图的起始点连一条边，边权与原边相同，代表逆向走一条边。逆向走了一条边，就不能再逆向走了，所以从上面的一层（新图）无法回到下面的一层。最后跑一遍SPFA，节点11所在的强连通分量编号，到节点1所在的强连通分量编号+N上的最长路，就是最后的答案。
SPFA判负环
需要注意的是，一定要先把x的vis标记设为0；
因为可能一个点连接着自己；
bool spfa(int st)
{
vis[st] = 1;
d[st] = 0;
q.push(st);
while(!q.empty())
{
int x = q.front();
q.pop();
vis[x] = 0;
++ci[x];
go[x] = 1;
if(ci[x] > n) return 1;
for(ri i = head[x]; i; i = nx[i])
if(d[v[i]] > d[x] + w[i])
{
d[v[i]] = d[x] + w[i];
if(!vis[v[i]])
{
vis[v[i]] = 1;
q.push(v[i]);
}
}
}
return 0;
}树上路径相交问题
给定一棵树，每次询问两条树上的路径有无重叠；
当然可以裸上树剖，loglog
不妨设
当然有一个剪枝：如果一对点的lca深度大于另外一对点的深度的最大值，一定无解；
bool sol(int a, int b, int c, int d)
{
int p = lca(a, b), q = lca(c, d);
if(dep[p] > dep[q])
{
swap(p, q);
swap(a, c), swap(b, d);
}
if(dep[q] > max(dep[a], dep[b])) return 0;
if(lca(q, a) == q || lca(q, b) == q) return 1;
return 0;
}欧拉序求LCA
欧拉序是dfs序的一种，存放的是dfn；
两个点的lca是两个点第一次在欧拉序上出现的位置中间的序列的最小值，对应的节点编号；
欧拉序的长度为点数的两倍；
[POI2018]Pionek
感觉自己的几何能力还需要加强
你有N个二维向量，可以选择一些向量相加，使最后向量的模长最大；n<=200000
可以想见，如果我们确定了最终答案的方向，那么对答案有贡献的向量就是角度之差在
每次区间限制固定，要最大化长度：双指针法
不过要注意的是，不一定区间最长就最优，因为最终的答案不一定是给定的向量的方向，所以要步步取max；
王室联邦
题意：给定一棵树，将树分成若干块，每块大小为
使用DFS模拟栈，当前节点所属的栈的大小大于b就出栈，组成一个块；当前节点最后再入栈；（入栈之后是否检查块的大小都可以）
void dfs(int x, int fa)
{
int bot = top;
for(ri i = head[x]; i; i = nx[i])
if(v[i] != fa)
{
dfs(v[i], x);
if(top - bot >= b)
{
++cnt;
hui[cnt] = x;
while(top != bot)
{
bel[st[top]] = cnt;
--top;
}
}
}
st[++top] = x;
}偶度数子图个数
一张无向无权图，求图中每个点的度数大于零且都是偶数的子图的个数对1000000009取模的值
对于每一条非树边，都会贡献一个环，答案即为
维护非树边的个数可以用并查集，每次合并已经合并的集合，就是一条非树边；
树网的核
选取的路径一定是在直径上的，为什么？不在直径上，偏心距的最大值最小为
更好的方法是单调栈+尺取法；
但是可以二分mid，从直径的左右端点不停向中心走，直到到两端点的距离
无向图找最小环
无向图找最小环可以用bfs解决。即从每个点开始找到最小环就break（可以证明如果一个无向图的平均度数至少是8，那么它一定包含一个环。所以bfs时只要搜索最多5000*8条边，一定会找到环并break）。
给定一个有向图，要求找出一个环，其中可以有重点但是不能有重边，且环上的边方向是交错的。
见 Nowcoder-TG3-B
无向图删两点使不联通的方案数
枚举第一个点，tarjan一遍：
一个联通块：割点个数
两个联通块：1.都只有1个点：0；2.有一个只有1个点：n-2；3.n-1；
多个：n-1；
答案为上述相加除2；
差分约束优化常数
差分约束为了优化常数，有时不用建一个超级源点为每个前缀和强制非负，直接把sum0当成原点就好；
SPFA两个优化妥妥的负优化
Tarjan缩点双，出栈，直到弹出v[i] ，然后与x 一起构成v\text{-}dcc
带权最小环
1.无向图：Floyd；
Floyd的每个阶段，
2.有向图：Dij；
枚举起点s，扫描s的所有出边，加入到队列中，然后令
异象石
给定一棵树，维护一个集合，动态选择一些点加入/删除，每次询问使这些点联通的最小路径长度；
观察（？？？）得，答案即为：将点按照dfs序排序，围成一个环（1与n相邻），相邻两个点之间的路径长度和的一半；
易错点：begin和end的左右相邻，要注意判断
最高效的SPFA判负环是统计路径长度
树剖时，注意hsn初值为零，不能存在0号点
见博客<数论求并>
要求经过所有点的最短路，可以预处理出任意两个点的最短路后，DP转移，更快
圆桌骑士
给定一张无向图，求有多少点不被任何一个奇环包含；
几个性质：1.如果两个点不在一个点双，那么肯定没有奇环包括他们俩；2.如果一个点双内有一个奇环，那么点双内的所有点都被奇环包含；
Ants
平面上有n个白点，n个黑点；要求为每一个白点连接一个黑点，且这些线段不相交，问最终方案；
线段不相交，等价于选出的线段的长度和最小！，于是跑一个最小费用最大流即可；
二分图最大匹配的必须边和可行边
建图后跑网络流；
必须边的条件：
可行边的条件：
图论经典的点边转化
边转化成点，尤其在树上常用；
点转化成边：拆成入点和出点，入点和出点连边；
POJ 1966
给定一张无向图，最少删掉几个点，可以使图不联通；
枚举不联通的两个点，然后跑网络流，最大流等于最小割；
建图方式和上面一条说的一样，入点和出点连流量为1的边，原图的边流量为+inf；
Tarjan 与 2-sat
输出方案，比较的是scc编号，且编号小的为真；
判定最短路上的必经点
跑一边最短路，用最短路径数统计即可；
还有一种方法，在Floyd时统计：
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
if(i!=k)
for(int j=1;j<=n;j++)
if(i!=j&&j!=k)
{
if(e[i][j]>e[i][k]+e[k][j])
{
e[i][j]=e[i][k]+e[k][j];
city[i][j]=k;
}
else if(e[i][j]==e[i][k]+e[k][j])
city[i][j]=-1;
}统计任意两点最短路条数：
for(ri k=1;k<=n;++k)
for(ri i=1;i<=n;++i)
if(f[i][k]<f[0][0]) for(ri j=1;j<=n;++j)
{
if(f[i][j]==f[i][k]+f[k][j]) num[i][j]+=num[i][k]*num[k][j];
else if(f[i][j]>f[i][k]+f[k][j]) f[i][j]=f[i][k]+f[k][j],num[i][j]=num[i][k]*num[k][j];
}二分图是无向图，建边时最好建单向边，否则常数大；记得给左右部点不同编号；
能不递归dfs就不递归
bfs求dfs序
相同点：
先出来father的编号再出来son的编号。根节点都是1号。
区别：子树连续访问pk儿子连续访问。
联系：就差一个size
bfs求bfs序，再倒序记录每个点的size
然后，遍历bfs序。
这时x的fa一定已经求出了dfs序。
如果上一个点的fa和这个点的fa不同，那么x一定是x的fa的第一个儿子，到了fa之后就先访问x。dfn[x]=dfn[fa[x]]+1
如果上一个点的fa和这个点的fa相同，那么x一定是上一个点的后兄弟。dfn[x]=dfn[las]+size[las]
理解就是，dfs时会先遍历las的整个子树。并且下一个就一定是x了。
by Miracle
2-SAT 确定解/不定解
枚举每个点的解，跑一遍Tarjan看是否成立；如果01都成立就是不定解；