强联通分量
强连通：有向图 \(G\) 强连通表示，\(G\) 中任意两个结点连通。
强连通分量（ Strongly Connected Components ，简称 \(\operatorname{SCC}\) ）：极大的 强连通子图。
Tarjan
维护了以下两个变量：
-
\(dfn\) ：深度优先搜索遍历时结点 \(u\) 被搜索的次序 。
-
\(low\) ：设以 \(u\) 为根的子树为 \(subtree(u)\) 。 \(low\) 定义为以下结点的 \(dfn\) 的最小值： \(subtree(u)\) 中的结点；从 \(subtree(u)\) 通过 一条 不在搜索树上的边能到达的结点 。
从根开始的一条路径上的 \(dfn\) 严格递增，\(low\) 严格非降。
对于一个连通分量图，我们很容易想到，在该连通图中有且仅有一个 \(dfn[u]=low[u]\) 。该结点一定是在深度遍历的过程中，该连通分量中第一个被访问过的结点，因为它的 \(dfn\) 值和 \(low\) 值最小，不会被该连通分量中的其他结点所影响。
因此，在回溯的过程中，判定 \(dfn[u]=low[u]\) 的条件是否成立，如果成立，则栈中从 后面的结点构成一个 \(\operatorname{SCC}\) 。
P2341 [HAOI2006]受欢迎的牛 G \(-\) 模板
$\texttt{code}$
#define Maxn 10005
#define Maxm 50005
void tarjan(int u)
{
dfn[u]=low[u]=++Time; s.push(u),ins[u]=true;
for(int i=hea[u];i;i=nex[i])
{
if(!dfn[ver[i]]) tarjan(ver[i]),low[u]=min(low[ver[i]],low[u]);
else if(ins[ver[i]]) low[u]=min(dfn[ver[i]],low[u]);
}
if(dfn[u]==low[u])
{
sum+=1;
do
{
belong[u]=sum;
u=s.top(); s.pop(); ins[u]=false;
cnt[sum]+=1;
} while(dfn[u]!=low[u]);
}
}
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
时间复杂度 \(O(n+m)\) 。
Kosaraju
复杂度 \(O(n+m)\) 。
Garbow
复杂度 \(O(n+m)\) 。
我们可以利用强联通分量将一张图的每个强连通分量都缩成一个点。
然后这张图会变成一个 \(\operatorname{DAG}\)，可以进行拓扑排序以及更多其他操作 。
应用 \(-\) 缩点
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
for(int i=1;i<=tot[0];i++)
if(belong[fro[0][i]]!=belong[ver[0][i]])
add(1,belong[fro[0][i]],belong[ver[0][i]]),ind[belong[ver[0][i]]]++;
topo();
割点与桥
在无向图中删去这个点 \(/\) 边会使极大强联通增大，那么这个点 \(/\) 边为割点 \(/\) 桥 。
注意这里的 \(dfn\) 表示不经过父亲，能到达的最小的 \(dfn\) 。
割点
关键条件：
-
若 \(u\) 是根节点，当至少存在 \(2\) 条边满足 \(low[v] >= dfn[u]\) 则 \(u\) 是割点 。
-
若 \(u\) 不是根节点，当至少存在 \(1\) 条边满足 \(low[v] >= dfn[u]\) 则 \(u\) 是割点 。
$\texttt{code}$
void tarjan(int u,int fa)
{
dfn[u]=low[u]=++Time;
for(int i=hea[u];i;i=nex[i])
{
if(!dfn[ver[i]])
{
tarjan(ver[i],u),low[u]=min(low[ver[i]],low[u]);
if(low[ver[i]]>=dfn[u]) cnt[u]+=1;
}
else if(ver[i]!=fa) low[u]=min(dfn[ver[i]],low[u]);
}
}
for(int i=1;i<=n;i++) if(!dfn[i]) cnt[i]-=1,tarjan(i,0);
for(int i=1;i<=n;i++) if(cnt[i]>=1) ans+=1;
割边（桥）
关键条件：
- 当存在一条边条边满足 \(low[v] > dfn[u]\) 则边 \(i\) 是割边
关键部分的代码：
$\texttt{code}$
void tarjan(int u,int fa)
{
dfn[u]=low[u]=++Time;
for(int i=hea[u];i;i=nex[i])
{
if(!dfn[ver[i]])
{
tarjan(ver[i],u),low[u]=min(low[ver[i]],low[u]);
if(low[ver[i]]>dfn[u]) tag[i]=1; // 这条边是割边
}
else if(ver[i]!=fa) low[u]=min(dfn[ver[i]],low[u]);
}
}
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,0);
for(int j=2;j<=tot;j+=2) ans+=max(tag[j],tag[j^1]);
双联通分量
guguguing