Tarjan

一、割点和桥

P3469 [POI2008]BLO-Blockade

分类讨论。假设删取的点不是割点，那么对其他点并不会有影响，答案为 $2 \times (n - 2)$；否则的话，会产生若干个子树，以及剩下的点形成的连通块，答案为 $size_1 \times (n - size_1) + size_2 \times (n - size_2) + \cdots + size_n \times (n - size_n) + (sum + 1)\times (n - sum - 1)$。

Network

先 Tarjan 求出所有桥，每次询问后 $x$ 和 $y$ 到 $LCA(x,y)$ 把所有路上的桥都删去。

P5058 [ZJOI2004]嗅探器

题目所要求的其实就是 $a$ 和 $b$ 间的割点，只要在普通的 tarjan 上稍作修改即可。从 $a$ 开始 tarjan，若有点满足普通的割点的要求以及 $dfn_b\geq dfn_v$ 则 $u$ 是一个割点。

二、强连通分量

1. 简介

有向图 $G$ 强连通指 $G$ 中任意两个顶点连通（即在一个 简单环 中）。

强连通分量（SCC）是指极大的强连通子图。

强连通分量不会相交。因为强连通分量是极大的，若两个强连通分量相交只会形成一个更大的强连通分量。

若把强连通分量所为一个点，则得到一个有向无环图（DAG）。因为环就是一个强连通分量。

2. 例题

P3119 [USACO15JAN]Grass Cownoisseur G

在有向图中，且点可以重复经过，可以缩点。

然后有逆行的特殊操作，可以用分层图再跑 spfa 求最长路。

P2746 [USACO5.3]校园网Network of Schools

显然一个强连通分量中一个点接受到了整个强连通分量都会接受到，因此我们 Tarjan 后缩点，第一问的答案就是新图中入度为 $0$ 的点的个数。第二问答案是入度为 $0$ 和 出度为 $0$ 的点数中较大的那个。

P2272 [ZJOI2007]最大半连通子图

显然一个强连通分量中的点都是满足条件的，因此我们 tarjan 缩点成一个 DAG，然后在 DAG 上跑记忆化搜索求最长路。还要求方案数，只要用个 map 存一下方案数就好了。

P2515 [HAOI2010]软件安装

原图中可能有环，因此考虑 tarjan 缩点。缩完之后图一定是棵树，然后根据 dfs 序 dp 转移。

P1262 间谍网络

显然缩点后度数为 $0$ 的点都要收买，若无法收买则无解，否则的话就加上这个强连通分量中最小的收买。

三、边双连通分量

1. 简介

双连通分量与强连通分量类似，只不过是在无向图中，同时定义也有些变化。而边双连通分量是指

2. 例题

P2860 [USACO06JAN]Redundant Paths G

题目显然是让你连最少的边让整棵树都是边双连通分量。可以发现，连叶节点一定是最优的，因此先求边双连通分量缩点，再计算读度数为 $1$ 的点，答案就是 $(num+1) / 2$。

四、点双连通分量

1. 代码

void tarjan(int u, int fa) {
   dfn[u] = low[u] = ++dfs_cnt;
   s.push(u);
   for(int i = he[u]; i; i = e[i].nxt) {
   	int v = e[i].to;
   	if(v == fa)
   		continue;
   	if(!dfn[v]) {
   		tarjan(v, u);
   		low[u] = min(low[u], low[v]);
   		if(low[v] >= dfn[u]) {
   			dcc_cnt++;
   			while(1) {
   				int x = s.top();
   				s.pop();
   				dcc[dcc_cnt].push_back(x);
   				if(x == v)
   					break;
   			}
   			dcc[dcc_cnt].push_back(u);
   		}
   	}
   	else 
   		low[u] = min(low[u], dfn[v]);
   }
}

2. 例题

SP2878 KNIGHTS - Knights of the Round Table

用到一个关键性质：点双连通分量中有奇环，则所有点都至少在一个奇环上。因此我们建立除了互相讨厌的人之外的所有边（即 补图），然后在图上求所有的点双连通分量，求奇环的话，可以想到用二分图染色（因为二分图没有奇环）。