图论：强连通分量【SCC】

• 在有向图G中，如果两个顶点u，ｖ间有一条从ｕ到ｖ的有向路径，同时还有一条从ｖ到ｕ的有向路径，则称两个顶点强连通。

• 如果有向图G的每两个顶点都强连通，称G是一个强连通图。

• 有向非强连通图的极大强连通子图，称为强连通分量。

如何求解强连通分量？这里介绍Tarjan 算法

首先考虑强连通分量的性质，即存在一条回路能从初始点又回到初始点。在这个查找的过程中，可以对经过的结点标记，当发现某一节点连向的点正好以及被标记过，则说明找到了一条回路，而这个回路上的所有点构成一个强连通分量（即dfnᵤ＝loωᵤ ）。

为了保存这个强连通分量，我们需要知道这条路上有哪些点，而此时，栈就是一种适合该算法的数据结构。对于每次搜索的点，我们都加入栈中，遇到回路时，在把栈中的元素逐个弹出，记录它们的起始结点，直到栈中弹出的元素正好是起始结点时，结束弹栈，继续搜索其它强连通分量。

在这个过程中，所有的点和都有的边都被遍历了一次，所以最终的时间复杂度为O(N+M)

Tarjan算法的实现(基于深度优先搜索)

dfnᵤ：记录搜索顺序的数组dfn(时间戳)

loωᵤ：在u的子树中能够回溯到的最早的已经在栈中的结点。或者说: 从 i 出发可以走任意边，但走的最后一条边必须是回边的情况下，能够达到的所有点中 dfn 值最小的是多少。

一个栈s[n]存储搜索路径；

instack[MAXN]：第 i个点在不在栈里面。

ans数组表示第几个强连通分量里的元素集合

设以u为根的子树为tree。loωᵤ 定义为以下结点的dfn的最小值：tree中的结点；从tree通过一条不在搜索树上的边能到达的结点。

表示某结点是否在栈中的数组instack；

我们视每个连通分量为搜索树中的一棵子树，在搜索过程中，维护一个栈，每次把搜索树中尚未处理的节点加入栈中。

按照深度优先搜索算法搜索的次序对图中所有的结点进行搜索，维护每个结点的dfn与low变量，且让搜索到的结点入栈。每当找到一个强连通元素，就按照该元素包含结点数目让栈中元素出栈。在搜索过程中，对于结点u和与其相邻的结点v (v不是u的父节点) 考虑三种情况

1. v未被访问：继续对v进行深搜。回溯过程中用 loωυ 更新 loωᵤ 。因为存在从u到v的直接路径，所以v能回溯到的已经在栈中的节点，u也一定能回溯到

2. v被访问过，已经在栈中，根据low值的定义，用dfnυ 更新 loωᵤ

3. v被访问过，已不在栈中，说明v已搜索完毕，其所在连通分量已被处理，所以不用对其做操作。

int dfn[N], low[N], dfncnt, s[N], instack[N], tp;//tp代表栈里有几个点

int scc[N], sc; // 结点 i 所在 SCC 的编号,sc代表强连通分量的数目

int sz[N]; // 强连通 i 的大小

void tarjan(int u) {

low[u] = dfn[u] = ++dfncnt, s[++tp] = u, instack[u] = 1;

for (auto i:g[u]) {

const int &v = i;

if (!dfn[v]) {

tarjan(v);

low[u] = min(low[u], low[v]);

} else if (instack[v]) {

low[u] = min(low[u], dfn[v]);

}

}

if (dfn[u] == low[u]) {

++sc;

ans[sc].push_back(u);

while (s[tp] != u) {

scc[s[tp]] = sc;

sz[sc]++;

instack[s[tp]] = 0;

ans[sc].push_back(s[tp]);

--tp;

}

scc[s[tp]] = sc;

sz[sc]++;

instack[s[tp]] = 0;

--tp;

}

}

数学联邦政治世界观提示您：看后求收藏（笔尖小说网http://www.bjxsw.cc），接着再看更方便。