最短路
差分约束
生成树
AGC004D
有 \(n\) 个城市，每个城市有一个传送点，都可以传送到唯一的一个城市，保证从任何位置出发经过若干次传送之后能够到达 \(1\) 号城市。现在希望修改一些点的目的地，使得从任何一点出发在传送 \(K\) 次之后恰好都能到达 \(1\) 号城市，求最少要改变目的地的城市的数量。
P4768
本题的故事发生在魔力之都，在这里我们将为你介绍一些必要的设定。
魔力之都可以抽象成一个 \(n\) 个节点、\(m\) 条边的无向连通图（节点的编号从 \(1\) 至 \(n\)）。我们依次用 \(l,a\) 描述一条边的长度、海拔。
作为季风气候的代表城市，魔力之都时常有雨水相伴，因此道路积水总是不可避免的。由于整个城市的排水系统连通，因此有积水的边一定是海拔相对最低的一些边。我们用水位线来描述降雨的程度，它的意义是：所有海拔不超过水位线的边都是有积水的。
Yazid 是一名来自魔力之都的 OIer，刚参加完 ION2018 的他将踏上归程，回到他温暖的家。Yazid 的家恰好在魔力之都的 \(1\) 号节点。对于接下来 \(Q\) 天，每一天 Yazid 都会告诉你他的出发点 \(v\) ，以及当天的水位线 \(p\)。
每一天，Yazid 在出发点都拥有一辆车。这辆车由于一些故障不能经过有积水的边。Yazid 可以在任意节点下车，这样接下来他就可以步行经过有积水的边。但车会被留在他下车的节点并不会再被使用。
需要特殊说明的是，第二天车会被重置，这意味着：
- 车会在新的出发点被准备好。
- Yazid 不能利用之前在某处停放的车。
Yazid 非常讨厌在雨天步行，因此他希望在完成回家这一目标的同时，最小化他步行经过的边的总长度。请你帮助 Yazid 进行计算。
本题的部分测试点将强制在线，具体细节请见【输入格式】和【子任务】。
图的连通性
强连通分量
B3609
给定一张 \(n\) 个点 \(m\) 条边的有向图，求出其所有的强连通分量。
注意，本题可能存在重边和自环。
输出格式：
第一行一个整数表示这张图的强连通分量数目。
接下来每行输出一个强连通分量。第一行输出 1 号点所在强连通分量，第二行输出 2 号点所在强连通分量，若已被输出，则改为输出 3 号点所在强连通分量，以此类推。每个强连通分量按节点编号大小输出。
P2341
每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果 \(A\) 喜欢 \(B\)，\(B\) 喜欢 \(C\)，那么 \(A\) 也喜欢 \(C\)。牛栏里共有 \(N\) 头奶牛，给定一些奶牛之间的爱慕关系，请你算出有多少头奶牛可以当明星。
P2272
一个有向图 \(G=\left(V,E\right)\) 称为半连通的 (Semi-Connected)，如果满足：\(\forall u,v\in V\)，满足 \(u\to v\) 或 \(v\to u\)，即对于图中任意两点 \(u,v\)，存在一条 \(u\) 到 \(v\) 的有向路径或者从 \(v\) 到 \(u\) 的有向路径。
若 \(G'=\left(V',E'\right)\) 满足 \(V'\subseteq V\)，\(E'\) 是 \(E\) 中所有跟 \(V'\) 有关的边，则称 \(G'\) 是 \(G\) 的一个导出子图。若 \(G'\) 是 \(G\) 的导出子图，且 \(G'\) 半连通，则称 \(G'\) 为 \(G\) 的半连通子图。若 \(G'\) 是 \(G\) 所有半连通子图中包含节点数最多的，则称 \(G'\) 是 \(G\) 的最大半连通子图。
给定一个有向图 \(G\)，请求出 \(G\) 的最大半连通子图拥有的节点数 \(K\)，以及不同的最大半连通子图的数目 \(C\)。由于 \(C\) 可能比较大，仅要求输出 \(C\) 对 \(X\) 的余数。
CF1239D
有 \(n\) 个人和 \(n\) 只猫，人和猫都以 \(1\sim n\) 编号，第 \(i\) 个人是第 \(i\) 只猫的主人。每个人都认识一些猫（其中包括自己的猫）。
要求选出 \(j\) 名裁判（人）和 \(p\) 只选手（猫），使得 \(j+p=n\)，且 \(1<j,p<n\)，且选出的任何人都不认识任何一只猫。
如果不存在这样的方案输出一行No。
如果存在则第一行输出Yes，第二行输出两个数字分别代表裁判和选手的数量，第三行输出所有裁判的编号，第四行输出所有选手的编号。
ARC092F
- 有一个 \(N\) 个点 \(M\) 条边的有向图。保证图中不存在重边和自环。
- 试判断将每条边反向，其他边不变的情况下，图中强连通分量的数量是否改变。
- 若改变，输出
diff，否则输出same。- \(1 \leq N \leq 10^3\)，\(1 \leq M \leq 2 \times 10^5\)。
UOJ134
CF1142E
给定一张 \(n\) 个点的竞赛图。边分为粉色和绿色。粉色的边有 \(m\) 条，你已经知道了它们的方向。而绿色的边你不知道方向。
每次询问，你可以获得一条绿色的边的方向。
你需要在 \(2n\) 次询问内，找到一个点 \(u\)，使得对于每个点 \(v\)，都有一条 \(u\to v\) 的路径，使得路径上每条边同色。需要注意的是路径只能通过粉边和你已经询问的绿边。
交互库是自适应的。
\(n, m \leq 10^5\)。
割点
P3388
给出一个 \(n\) 个点，\(m\) 条边的无向图，求图的割点。