关于图的连通性：连通分量、割点、割边……

一个图的连通分量就是一个图中所有能互通的点组成的集合。一个连通图的连通分量只有个。

一个连通分量里，如果把某个点删除了之后，这个连通分量就会断开，变成多个，那么这个点就是割点。一个连通分量里可能有多个割点。相应的，如果删除某条边会断开一个连通分量，那这条边就是一条割边。

首先我们来讲无向图的连通性。

无向图

连通无向图求割点

现在，你有一个无向连通图。请问怎么求割点？

我们首先以一个点为根，求一个 DFS 树。求出来这棵树了之后，可能会有一些回退边。下面有两个定理：

定理：如果一棵树的根要成为割点，那么他一定要有个儿子（这里指的是下一层）。

证明：树的根是肯定没有回退边的，于是要删除他之后让一个连通分量断为多个，只能让他有多个儿子。

定理：如果一棵树的非根节点要成为割点，那么就一定存在一个儿子（也指的是下一层），并且及的后代都没有一条回退边连向的祖先（不包括）。

证明：如果的某一个儿子存在一个后代点连向的祖先，那么你断掉点了之后下面的点也可以通过的回退边回到的祖先，~~再回到已经不存在的点~~。

而如果有一个点他的后代不存在连向祖先的回退边，那么断掉，后面的点没有回到他祖先的边，然后这些点就只能自己成一个连通分量了。

介绍完这两个定理之后，定理是好实现的，那么定理怎么实现呢？

我们定义两个数组：和。表示点的 DFS 序。如果在一条固定的链上，若点的 DFS 序小于的，那么就说明为的祖先。表示点和的后代能跳到的祖先的。

根据定理，只要存在一个为的直接儿子，并且，那么就说明点就是一个割点。

数组只需通过 DFS 取得，现在我们要实现数组的更新。

我们知道，如果一个点有一个后代，他有回退边，那么我们就可以用来更新。然后递归回去的时候，（指的是直接儿子）。

就是说，我们可以从这个点往下跑到回退边，然后再通过回退边来到正在 DFS 的这条链上的祖先。然后再对这些取最小值。

于是，我们就可以愉快的求出和数组，并且判断这个点是否为割点了！

//iscut 数组：表示 i 点是否为割点。
void dfs(int x, int fa){
    int soncnt = 0;
    low[x] = dfn[x] = ++idx;
    for(int i=h[x];i;i=edge[i].nxt){
        int v = edge[i].to;
        if(!dfn[v]){
            soncnt++;
            dfs(v, x);
            low[x] = min(low[x], low[v]);
            if(low[v] >= dfn[x] && x != 1){
                iscut[x] = 1;
            }
        }else if(v != fa){
            low[x] = min(low[x], dfn[v]);
        }
    }
    if(x==1 && soncnt >= 2) iscut[x] = 1;
}

连通无向图求割边

先说结论：只要把改为即可！

考虑的意思是从及其儿子最远可以跳到 及后代。而表示的就是从及其儿子最远可以跳到 的后代，不包括 x。因为我们求的是割边，如果从跳到了，而又不像割点一样，它这次并没有被删除。所以还是能连通（例如上图的的这条边和的关系。是割点，但不是割边）。所以如果，那么边就是一条割边。其他的和割点一模一样。

点双连通分量

现在你有两个点。如果你从点到点可以通过大于条点不重复的路径，那么我们就说这两个点点双连通。而很多个这样子的点组合起来就变成了点双连通分量。根据定义，如果你删掉了这个点双连通分量的任意一个点，那么这个图的连通性不会改变。也就是说，点双连通分量没有割点。

对应的，还有边双连通分量。这个就是删除了任意一条边，连通性不会改变，边双连通分量里面没有割边。

我们根据点双连通分量没有割点这个定理，就说明一个割点就连接了多个点双连通分量。那就可以使用和之前求割点类似的方法来求。

方法如下：

我们用一个栈，来存储目前已经遍历过的点。你调用 dfs 函数一次，栈就把这个点给 push 进去。容易发现，当 dfs 函数从的儿子递归回的时候，那么就说明及的后代都已经被装到栈里面了。

如果这个点是割点（这个时候的割点就不考虑根的限制，某个点成为“割点”的条件只有），那么就说明点、点及的后代就是一个点双连通分量。首先把及的后代都从栈里面 pop 出来，然后再把它们 push_back 到新的一个点双连通分量存储数组（vector 型）里面去。然后再把 push_back 到存储数组里。注意这里的不用从栈里 pop 出来！！！

这样也可以规避的后代也有割点的问题，因为的后代的那个割点的后代已经不在栈里面了。就相当于是已经被分成了两部分。

注意：一个单独的点，他也可以成为一个点双连通分量。

于是我们就可以愉快的写代码了：

int low[N], dfn[N];
int idx;
int st[N], pos;
vector<int> ans[N];
int anslen;
void dfs(int x, int fa){
	low[x] = dfn[x] = ++idx;
	st[++pos] = x;
	int soncnt = 0;
	for(int i=h[x];i;i=edge[i].nxt){
		int v = edge[i].to;
		if(!dfn[v]){
			soncnt ++;
			dfs(v, x);
			low[x] = min(low[x], low[v]);
			if(low[v] >= dfn[x]){
				++anslen;
				int lstpop;
				do{
					lstpop = st[pos--];
					ans[anslen].push_back(lstpop);
				}while(lstpop != v);
				ans[anslen].push_back(x);
			}
		}else if(v != fa){
			low[x] = min(low[x], dfn[v]);
		}
	}
	if(soncnt == 0 && fa == 0){
		ans[++anslen].push_back(x);
	}
}

边双连通分量

这个和点双连通分量相似，一条割边连接了多个边双连通分量。

于是我们可以把割边全部删除，剩下的连通块个数就是边双连通分量个数，然后每一个连通块就是一个边双连通分量！

于是，代码来了：

int low[N], dfn[N], idx;
bool iscuted[M<<1];
void dfs(int x, int lastedge){
    low[x] = dfn[x] = ++idx;
    for(int i=h[x];i;i=edge[i].nxt){
        int v = edge[i].to;
        if(!dfn[v]){
            dfs(v, i);
            low[x] = min(low[x], low[v]);
            if(low[v] > dfn[x]){
                iscuted[i] = iscuted[i^1] = 1;
            }
        }else if(i != (lastedge^1)){
            low[x] = min(low[x], dfn[v]);
        }
    }    
}
vector<int> ans[N];

int len=0;
bool vis[N];
void dfstoget(int x, int idx){
    vis[x] = 1;
    ans[idx].push_back(x);
    for(int i=h[x];i;i=edge[i].nxt){
        if(iscuted[i]) continue;
        int v = edge[i].to;
        if(vis[v]) continue;
        dfstoget(v, idx);
    }
}

无向图的介绍先到这里，我们来介绍有向图。

有向图

有向图有一种连通状态，叫强连通。强连通就是两个点互相可达。

而强连通分量（SCC）就是一个图的子图，这个子图是强连通图并且这个子图扩展到了最大，那么这个子图就是原图的一个强连通分量。一个有向图里面可能有很多个强连通分量。

于是我们接下来的问题就是怎么求一个有向图中的所有强连通分量。

强连通分量

强连通分量有一个非常重要的定理：

在一个强连通分量里，从一个点出发，一定能通过某条路径到达他自己。

于是我们可以用之前求割点的和技术，来解这一道题。

根据上面的这个定理，我们可以得到，如果一些点的值相同，那么这些点都属于一个强连通分量。

我们可以这个时候我们可以暴力，处理完了之后将相同的值分到一起，然后每一个相同的就是一个强连通分量，最后统计就行。

但是有一个更好的方法：

我们建一个栈，像求割点一样。这个栈每遍历一个点，就把这个点加进栈里面。考虑最先入栈的点，他一定是所有值等于的强连通分量的最老的祖先。这个祖先的。

然后把这个子树里面的所有点全部加进一个强连通分量。直到栈中的点等于（此时也应该被 pop 出去）。

然后我们就可以愉快的写代码了：

void dfs(int x, int fa){
    low[x] = dfn[x] = ++idx;
    st[++pos] = x;
    for(int i=h[x];i;i=edge[i].nxt){
        int v = edge[i].to;
        if(!dfn[v]){
            dfs(v, x);
            low[x] = min(low[x], low[v]);
        }else if(!sccin[v]){
            low[x] = min(low[x], dfn[v]);
        }
    }
    if(low[x] == dfn[x]){
        int lstpop=0;
        len++;
        do{
            lstpop = st[pos];
            pos--;
            scc[len].push_back(lstpop);
            sccin[lstpop] = len;
        }while(lstpop != x);
    }
}

注释：这里的 !sccin[v] 的意思就是这个你要递归下去的那个点是否已经被确定为一个强连通分量。如果他已经被定性为属于一个强连通分量，那么那个点已经被更新完毕，不能用来更新当前点。跳过。

小拓展：缩点

缩点就是利用强连通分量的点两两可互相到达的性质，把一个强连通分量缩成一个点。

需要重新建一个图，然后遍历原来的那个图的所有边，每一条边判一下连接的两个点是否在一个强连通分量里。如果在则新图不连边，否则连边。

for(int i=1;i<=cnt;i++){
    int u = edge[i].from, v = edge[i].to;
    int uidx = sccin[u], vidx = sccin[v];
    if(uidx != vidx){
        readd(uidx, vidx);
        // cerr<<uidx<<" -> "<<vidx<<'\n';
        indeg[vidx] ++, outdeg[uidx] ++;
    }
}

接下来我们以几道例题来讲一讲这些玩意的用法。

P3225

这道题因为题目说了，“使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口”，所以很容易想到，一个点到出口有至少两条路径可达。所以我们很容易想到点双连通分量和割点。

然后如果整个图是一个点双连通分量，这个分量首先可以放一个点，如果其他某点消失了剩余的点也可以到达出口。但是如果这个出口消失了那么就没路可走了。于是你只能放两个出口。放置方案数即为。

而如果一堆的割点和一堆的点双连通分量一起组成了一棵树状结构的话，那么你肯定至少是有个点双的。这个时候，你只需要在每一个“叶子”点双（就是这个点双里只有个割点）里放个出口就行了。因为如果他不是“叶子”点双的话，你可以通过其他的点双转移过来。因为他至少有个割点，就说明有个其他点双连接到他上面。就算你把某一个割点给堵了，也可以通过另外的割点到达其他出口。

所以我们只需判断所有的“叶子”点双，然后出口总数就是叶子点双的数量。放置方案数就是每一个叶子点双的的乘积。因为割点不能选。

于是就做出来了。

P2812

此题比上一道题简单。这个就是把所有强连通分量缩点了之后，第一问的答案就是入度为的点的个数，第二问的答案就是 $入度为的点的个数出度为的点的个数$ 。

此外需要特判如果这个图就是一个强连通图。这个时候第一问的答案就是。因为这时第一问的答案是没错，但是第二问的答案会变成。所以要特判一下，因为第二问的正确答案是。

P4819

这道题我们先缩点，然后一个很显然的事情是这个时候，你只要把入度为的所有强连通分量给选了，统计它的个数为，如果还没有死，那么杀手就一定能根据现有的数据推出来，因为选的都是起点。我们要选个点，而杀手会在个点里面等概率出现。所以，概率至少是。

而有一种特殊情况，请看下图：

容易发现，这种情况的最优选项应该是先选这个分量，然后不选。因为这个点是可以通过排除法排除出来的。如果说出了杀手的位置，那么就一定在这些点里。而如果这些点没有杀手，那杀手就只能是了。我们没必要，也不能去冒这个险选。

所以这种情况的概率就是。

把他推广到全局上来，什么样的情况的概率才是呢？还是用上面的排除法。你要减去，那就说明有一个大小为并且入度为的分量在最后还没有被确定。但是也不是所有大小为并且入度为的分量都可以这样。比如说这个样子：

这样的话点不能被排除，因为有一个点很碍事，在这里挡着。点也不能被排除，因为这个点也在这里挡着。那么第一张图为什么就有点可以排除呢？因为你发现，大小为连着的分量他有个入度！

个入度就说明，一个入度是大小为的分量贡献给他的，另外的入度（们）就是其他入度为的分量一直往下搜，可以搜到他。所以他最后可以被排除。

所以我们可以得出结论，一个图他要是概率为，那么就必须存在一个分量，他连着的所有点的入度都必须。

于是就可以做。

并且这道题有些小细节：建新图时要去除重边！

P3119

这道题还是先缩点。缩了就变成了一个 DAG。

因为是最多只能有一次逆行，所以答案的初始值就是起点所在的强连通分量的大小。

注意到这道题要求出的是类似这样的环的分量的总点数：

于是我们可以求出起点到每一个点的最长路，和每一个点到起点的最长路。

然后枚举每一条边，那么当前答案就是。这里的指的就是起点所在的强连通分量的大小。因为算重复了一次，所以要把他减掉。

因为这个图是一个 DAG，求最长路可以用拓扑排序解决。

最后答案就是。

以上。

Auth0r: 11400F, 11490DX.