强连通分量

HourSkit · 2024-11-16 09:05:23 · 算法·理论

~~ps: 这玩意肥肠仇项~~

注意: 文中关于Tarjan算法的具体内容出现过很多次，一处看不懂没关系，直接跳都可以，尤其是Tajan会反复说明、重申、补充

强连通分量 (概念)

可以看这个 blog

在有向图 G 中，如果两个顶点 u,v 间有一条从 u 到 v 的有向路径，同时还有一条从 v 到 u 的有向路径，则称两个顶点强连通。如果有向图 G 的每两个顶点都强连通，称 G 是一个强连通图。有向非强连通图的极大强连通子图，称为强连通分量

wiki: 强连通的定义是：有向图 G 强连通是指，G 中任意两个结点连通

说人话：

强连通图：

若从顶点 v 到 m 有路径，则称这俩顶点时强连通的。若任意一对顶点都是强连通的，称此图为强连通图

其实就是 u 可以到 v,v 也可以到 u (因为是无向图嘛)

强连通分量(SCC)：

有向图中的极大强连通子图称为有向图的强连通分量

就是在有向图中去找一个极大的子图 G, 且 G 是强连通图，极大就是额，尽可能的大吧

图中，子图 {1,2,3,4} 为一个强连通分量，因为顶点 1,2,3,4 两两可达。{5},{6} 也分别是两个强连通分量。

P3387 【模板】缩点

这是 tarjan 的板子题

那么来学 tarjan:

DFS 生成树：

有向图的 DFS 生成树主要有 4 种边（不一定全部出现）：

树边（tree edge）：示意图中以黑色边表示，每次搜索找到一个还没有访问过的结点的时候就形成了一条树边。

反祖边（back edge）：示意图中以红色边表示（即 7 \to 1），也被叫做回边，即指向祖先结点的边。

横叉边（cross edge）：示意图中以蓝色边表示（即 9 \to 7），它主要是在搜索的时候遇到了一个已经访问过的结点，但是这个结点并不是当前结点的祖先。

前向边（forward edge）：示意图中以绿色边表示（即 3 \to 6），它是在搜索的时候遇到子树中的结点的时候形成的。

我们考虑 DFS 生成树与强连通分量之间的关系：

如果结点 u 是某个强连通分量在搜索树中遇到的第一个结点，那么这个强连通分量的其余结点肯定是在搜索树中以 u 为根的子树中。结点 u 被称为这个强连通分量的根

tarjan 算法逻辑

以下内容来自wiki

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

接下来，对于每个节点u,维护2个变量dfn[i]和low[i]

\textit{dfn}_u: dfs时搜索次序

\textit{low}_u：在 u 的子树中能够回溯到的最早的已经在栈中的结点。设以 u 为根的子树为 \textit{Subtree}_u。\textit{low}_u 定义为以下结点的 \textit{dfn} 的最小值：\textit{Subtree}_u 中的结点；从 \textit{Subtree}_u 通过一条不在搜索树上的边能到达的结点。

一个结点的子树内结点的 dfn 都大于该结点的 dfn。

从根开始的一条路径上的 dfn 严格递增，low 严格非降。

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

1.v 未被访问：继续对 v 进行深度搜索。在回溯过程中，用 \textit{low}_v 更新 \textit{low}_u。因为存在从 u 到 v 的直接路径，所以 v 能够回溯到的已经在栈中的结点，u 也一定能够回溯到。

2.v 被访问过，已经在栈中：根据 low 值的定义，用 \textit{dfn}_v 更新 \textit{low}_u。

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

对于一个连通分量图，我们很容易想到，在该连通图中有且仅有一个 u 使得 \textit{dfn}_u=\textit{low}_u。该结点一定是在深度遍历的过程中，该连通分量中第一个被访问过的结点，因为它的 dfn 和 low 值最小，不会被该连通分量中的其他结点所影响。

因此，在回溯的过程中，判定 \textit{dfn}_u=\textit{low}_u 是否成立，如果成立，则栈中 u 及其上方的结点构成一个 SCC(强连通分量)。

int dfn[N], low[N], dfncnt, s[N], in_stack[N], tp;
int scc[N], sc;  // 结点 i 所在 SCC 的编号
int sz[N];       // 强连通 i 的大小

void tarjan(int u) {
  low[u] = dfn[u] = ++dfncnt, s[++tp] = u, in_stack[u] = 1;
  for (int i = h[u]; i; i = e[i].nex) {
    const int &v = e[i].t;
    if (!dfn[v]) {
      tarjan(v);
      low[u] = min(low[u], low[v]);
    } else if (in_stack[v]) {
      low[u] = min(low[u], dfn[v]);
    }
  }
  if (dfn[u] == low[u]) {
    ++sc;
    while (s[tp] != u) {
      scc[s[tp]] = sc;
      sz[sc]++;
      in_stack[s[tp]] = 0;
      --tp;
    }
    scc[s[tp]] = sc;
    sz[sc]++;
    in_stack[s[tp]] = 0;
    --tp;
  }
}

复杂度O(n+m)

看不懂，对吧?

~~那就只好...~~

优秀图解BLOG

~~这边也是获取了一下TA的精华~~

题面:

参考博客

【模板】缩点

题目描述

给定一个 n 个点 m 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。

允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。

输入格式

第一行两个正整数 n,m

第二行 n 个整数，其中第 i 个数 a_i 表示点 i 的点权。

第三至 m+2 行，每行两个整数 u,v，表示一条 u\rightarrow v 的有向边。

输出格式

共一行，最大的点权之和。

为啥叫缩点呢?

缩点，就是把一张有向有环图中的环缩成一个个点，形成一个有向无环图

根据题目意思，我们只需要找出一条点权最大的路径就行了，不限制点的个数。那么考虑对于一个环上的点被选择了，一整条环是不是应该都被选择，这一定很优，能选干嘛不选。很关键的是题目还允许我们重复经过某条边或者某个点，我们就不需要考虑其他了。因此整个环实际上可以看成一个点

此题解法：

这道题的思路比较恶心：tarjan缩点+dp

现在给出一个有向有环图，那么这个图不是一个DAG，所以不能在这种图上做拓扑排序或其他有关DAG的操作了 ps:DAG->有向无环图

可以看出\{1,2,3\}是一个强连通分量

我们的目的首先就是求出所有的强连通分量然后再将其缩成一个点，便可将图转为一个DAG

那么问题就被化简成了确定每个强连通分量的根

然后使用Tarjan求SCC

找出scc之后，问题通常会变成两个部分

1、scc内部

2、scc之间

如果把每个scc看成一个点，则是DAG图，即建出一个新图

拓扑排序就可以求dp顺序（如果有DAGdp的话，建议加个拓扑）

（对于这道题的dp，拓扑无意义，所以可以跳过拓扑，直接dp）

对每个点都不断用他的入边的点更新他，取最大值，f[i]表示i点（缩点后）的经过点和最大值

w代表当前点，rdr数组代表w点的入边的点，dis数组是权值。

dp方程: f[w]=max(f[w],f[rdr[w][j-1]]+dis_[w]);

应该是在fz抄的老师的code:

#include <bits/stdc++.h>
using namespace std;

const int maxn = 10000 + 15;
int n, m, sum, tim, top, s;
int p[maxn], head[maxn], sd[maxn], dfn[maxn], low[maxn]; 
int stac[maxn], vis[maxn];                               
int h[maxn], in[maxn], dist[maxn];
struct EDGE
{
    int to;
    int next;
    int from;
} edge[maxn * 10], ed[maxn * 10];
void add(int x, int y)
{
    edge[++sum].next = head[x];
    edge[sum].from = x;
    edge[sum].to = y;
    head[x] = sum;
}
void tarjan(int x)
{
    low[x] = dfn[x] = ++tim;
    stac[++top] = x;
    vis[x] = 1;
    for (int i = head[x]; i; i = edge[i].next)
    {
        int v = edge[i].to;
        if (!dfn[v])
        {
            tarjan(v);
            low[x] = min(low[x], low[v]);
        }
        else if (vis[v])
        {
            low[x] = min(low[x], low[v]);
        }
    }
    if (dfn[x] == low[x])
    {
        int y;
        while (y = stac[top--])
        {
            sd[y] = x;
            vis[y] = 0;
            if (x == y)
                break;
            p[x] += p[y];
        }
    }
}
int topo()
{
    queue<int> q;
    int tot = 0;
    for (int i = 1; i <= n; i++)
        if (sd[i] == i && !in[i])
        {
            q.push(i);
            dist[i] = p[i];
        }
    while (!q.empty())
    {
        int k = q.front();
        q.pop();
        for (int i = h[k]; i; i = ed[i].next)
        {
            int v = ed[i].to;
            dist[v] = max(dist[v], dist[k] + p[v]);
            in[v]--;
            if (in[v] == 0)
                q.push(v);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max(ans, dist[i]);
    return ans;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &p[i]);
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(i);
    for (int i = 1; i <= m; i++)
    {
        int x = sd[edge[i].from], y = sd[edge[i].to];
        if (x != y)
        {
            ed[++s].next = h[x];
            ed[s].to = y;
            ed[s].from = x;
            h[x] = s;
            in[y]++;
        }
    }
    printf("%d", topo());
    return 0;
}

P3388 【模板】割点（割顶）

题目描述

给出一个 n 个点，m 条边的无向图，求图的割点。

输入格式

第一行输入两个正整数 n,m。

下面 m 行每行输入两个正整数 x,y 表示 x 到 y 有一条边。

输出格式

第一行输出割点个数。

第二行按照节点编号从小到大输出节点，用空格隔开。

tarjan图不一定联通。

割点

割点概念，应该很好理解：

在一个无向图中，如果删除某个顶点，这个图就不再连通（任意两点之间无法相互到达），那么这个顶点就是这个图的割点

图中的2号顶点就是割点，删除2号后，4,5不通，1,6也不通等等

优秀博客

很容易想到的方法是：依次删除每一个顶点，然后用dfs或者bfs来检查图是否依然连通。如果删除某个顶点后，导致图不再连通，那么刚才删除的顶点就是割点

这种方法的时间复杂度是O(N(N+M)) 暴力你还想咋样

自然是Tarjan

再次贴一遍CODE:

看解释先:

假如到了u后，图中还有顶点v是没有访问过的点，如何判断v在不经过u的情况下是否还能回到之前访问过的任意一个点？u是v的父亲，而之前访问过的顶点就是祖先。也就是如何检测v在不经过父亲u的情况下还能否回到祖先。那就是对v再进行一次dfs，但此次遍历不经过u，看能否回到祖先。不能u即为割点

再定义一个数组low来记录每个顶点在不经过父顶点时，能够回到的最小“时间戳”

对于某个顶点u，如果存在至少一个顶点 v（ u 的儿子），使得low[v]>=num[u]，即不能回到祖先，那么u点为割点

具体过程理解可以看这个blog

~~那我必然给他Ctrl+C来了~~

4 经过搜索后，没有回溯到比父亲 3 时间戳更小的点，low[4] ≥dfn[3] ,所以 3 为割点。

1为根，扫到3 和 7是3 和 7都没访问过，则1有2个子树，即1为割点

7和3一样，满足low[8]>=dfn[7],为割点

void tarjan(int u,int anc){
    dfn[u]=low[u]=++dfncnt;
    int child=0;
    for(auto v:g[u]){
        if(!dfn[v]){
            tarjan(v,anc),low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]&&u!=anc) cut[u]=true;//如果儿子的low值大于等于dfn，
            则代表其为儿子与其他非子树点相连的唯一途径
            if(u==anc) child++;
        }
        else low[u]=min(low[u],dfn[v]);
    }
    if(child>=2&&u==anc) cut[u]=true;//对根的处理

Tips:对于割点，很多初学者都会对于 low[u]=min(low[u],dfn[v]) 感觉奇怪，然而将其改为 low[u]=min(low[u],low[v]) 后，又会寄，这是因为问题出现在了割点上

每日CTJ：

int n,m,ans;
vector<int> g[N];
bool cut[N];

int dfn[N],low[N],dfncnt;
int st[N],top;
bool inst[N];
void tarjan(int u,int anc){
    dfn[u]=low[u]=++dfncnt;
    int child=0;
    for(auto v:g[u]){
        if(!dfn[v]){
            tarjan(v,anc),low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]&&u!=anc) cut[u]=true;//如果儿子的low值大于等于dfn，
            则代表其为儿子与其他非子树点相连的唯一途径
            if(u==anc) child++;
        }
        else low[u]=min(low[u],dfn[v]);
    }
    if(child>=2&&u==anc) cut[u]=true;//对根的处理
}

int main(){
    n=read(),m=read();
    for(int i=1,u,v;i<=m;i++){
        u=read(),v=read();
        g[u].pb(v);g[v].pb(u);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i,i);
    for(int i=1;i<=n;i++)
        if(cut[i]) ans++;
    printf("%d\n",ans);
    for(int i=1;i<=n;i++)
        if(cut[i]) printf("%d ",i);
    return 0;
}

割边

除了割点还有一种问题是求割边（也称桥），即在一个无向图中删除某条边后，图不再连通

只需将求割点的算法修改一个符号就可以。只需将low[v]>=num[u]改为low[v]>num[u]。

这是为什么呢？

low[v]和num[u]相等则表示还可以回到父亲结点；而low[v]>num[u]则表示连父亲都回不到了。倘若顶点v不能回到祖先，也没有另外的路能回到父亲，那么 u-v 这条边就是割边

双连通分量

def定义:

在一张连通的无向图中，对于两个点 u 和 v，如果无论删去哪条边（只能删去一条）都不能使它们不连通，我们就说 u 和 v 边双连通。

在一张连通的无向图中，对于两个点 u 和 v，如果无论删去哪个点（只能删去一个，且不能删 u 和 v 自己）都不能使它们不连通，我们就说 u 和 v 点双连通。

边双连通具有传递性，即，若 x,y 边双连通，y,z 边双连通，则 x,z 边双连通。

点双连通不具有传递性，反例如下图，A,B 点双连通，B,C 点双连通，而 A,C 不点双连通。

对于一个无向图中的极大边双连通的子图，我们称这个子图为一个边双连通分量

对于一个无向图中的极大点双连通的子图，我们称这个子图为一个点双连通分量

P8436 【模板】边双连通分量

~~stupid B~~

对于一张连通的无向图，我们可以从任意一点开始 DFS，得到原图的一棵 DFS 生成树（以开始 DFS 的那个点为根），这棵生成树上的边称作树边，不在生成树上的边称作非树边。

由于 DFS 的性质，我们可以保证所有非树边连接的两个点在生成树上都满足其中一个是另一个的祖先。

DFS 的代码如下：

void DFS(int p) {
  visited[p] = true;
  for (int to : edge[p])
    if (!visited[to]) DFS(to);
}

用 Tarjan 求双连通分量过程与求强连通分量类似，可以先阅读强连通分量的 Tarjan 算法。

我们考虑先求出所有的桥(割边)，再 DFS 求出边双连通分量。

时间复杂度 O(n+m)。

wiki CODE:

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
constexpr int N = 5e5 + 5, M = 2e6 + 5;
int n, m, ans;
int tot = 1, hd[N];

struct edge {
  int to, nt;
} e[M << 1];

void add(int u, int v) { e[++tot].to = v, e[tot].nt = hd[u], hd[u] = tot; }

void uadd(int u, int v) { add(u, v), add(v, u); }

bool bz[M << 1];
int bcc_cnt, dfn[N], low[N], vis_bcc[N];
vector<vector<int>> bcc;

void tarjan(int x, int in) {
  dfn[x] = low[x] = ++bcc_cnt;
  for (int i = hd[x]; i; i = e[i].nt) {
    int v = e[i].to;
    if (dfn[v] == 0) {
      tarjan(v, i);
      if (dfn[x] < low[v]) bz[i] = bz[i ^ 1] = true;
      low[x] = min(low[x], low[v]);
    } else if (i != (in ^ 1))
      low[x] = min(low[x], dfn[v]);
  }
}

void dfs(int x, int id) {
  vis_bcc[x] = id, bcc[id - 1].push_back(x);
  for (int i = hd[x]; i; i = e[i].nt) {
    int v = e[i].to;
    if (vis_bcc[v] || bz[i]) continue;
    dfs(v, id);
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  int u, v;
  for (int i = 1; i <= m; i++) {
    cin >> u >> v;
    if (u == v) continue;
    uadd(u, v);
  }
  for (int i = 1; i <= n; i++)
    if (dfn[i] == 0) tarjan(i, 0);
  for (int i = 1; i <= n; i++)
    if (vis_bcc[i] == 0) {
      bcc.push_back(vector<int>());
      dfs(i, ++ans);
    }
  cout << ans << '\n';
  for (int i = 0; i < ans; i++) {
    cout << bcc[i].size();
    for (int j = 0; j < bcc[i].size(); j++) cout << ' ' << bcc[i][j];
    cout << '\n';
  }
  return 0;
}

方法2：

我们先总结出一个重要的性质，在无向图中，DFS 生成树上的边不是树边就只有非树边。

我们联系一下求强连通分量的方法，在无向图中只要一个分量没有桥，那么在 DFS 生成树上，它的所有点都在同一个强连通分量中。

反过来，在 DFS 生成树上的一个强连通分量，在原无向图中是边双连通分量。

可以发现，求边双连通分量的过程实际上就是求强连通分量的过程。

时间复杂度 O(n+m)。

#include <algorithm>
#include <iostream>
#include <stack>
#include <vector>

using namespace std;
constexpr int N = 5e5 + 5, M = 2e6 + 5;
int n, m;

struct edge {
  int to, nt;
} e[M << 2];

int hd[N << 1], tot = 1;

void add(int u, int v) { e[++tot] = edge{v, hd[u]}, hd[u] = tot; }

void uadd(int u, int v) { add(u, v), add(v, u); }

int bcc_cnt, sum;
int dfn[N], low[N];
bool vis[N];
vector<vector<int>> ans;
stack<int> st;

void tarjan(int u, int in) {
  low[u] = dfn[u] = ++bcc_cnt;
  st.push(u), vis[u] = true;
  for (int i = hd[u]; i; i = e[i].nt) {
    int v = e[i].to;
    if (i == (in ^ 1)) continue;
    if (!dfn[v])
      tarjan(v, i), low[u] = min(low[u], low[v]);
    else if (vis[v])
      low[u] = min(low[u], dfn[v]);
  }
  if (dfn[u] == low[u]) {
    vector<int> t;
    t.push_back(u);
    while (st.top() != u)
      t.push_back(st.top()), vis[st.top()] = false, st.pop();
    st.pop(), ans.push_back(t);
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  int u, v;
  for (int i = 1; i <= m; i++) {
    cin >> u >> v;
    if (u != v) uadd(u, v);
  }
  for (int i = 1; i <= n; i++)
    if (!dfn[i]) tarjan(i, 0);
  cout << ans.size() << '\n';
  for (int i = 0; i < ans.size(); i++) {
    cout << ans[i].size() << ' ';
    for (int j = 0; j < ans[i].size(); j++) cout << ans[i][j] << ' ';
    cout << '\n';
  }
  return 0;
}

WIKI链接

P8435 【模板】点双连通分量

题目描述

对于一个 n 个节点 m 条无向边的图，请输出其点双连通分量的个数，并且输出每个点双连通分量。

Solve:

来自wiki:

先给出两个性质：

两个点双最多只有一个公共点，且一定是割点。

对于一个点双，它在 DFS 搜索树中 dfn 值最小的点一定是割点或者树根。我们根据第二个性质，分类讨论：

当这个点为割点时，它一定是点双连通分量的根，因为一旦包含它的父节点，他仍然是割点。

当这个点为树根时：

有两个及以上子树，它是一个割点。

只有一个子树，它是一个点双连通分量的根。

它没有子树，视作一个点双。

#include <iostream>
#include <vector>
using namespace std;
constexpr int N = 5e5 + 5, M = 2e6 + 5;
int n, m;

struct edge {
  int to, nt;
} e[M << 1];

int hd[N], tot = 1;

void add(int u, int v) { e[++tot] = edge{v, hd[u]}, hd[u] = tot; }

void uadd(int u, int v) { add(u, v), add(v, u); }

int ans;
int dfn[N], low[N], bcc_cnt;
int sta[N], top, cnt;
bool cut[N];
vector<int> dcc[N];
int root;

void tarjan(int u) {
  dfn[u] = low[u] = ++bcc_cnt, sta[++top] = u;
  if (u == root && hd[u] == 0) {
    dcc[++cnt].push_back(u);
    return;
  }
  int f = 0;
  for (int i = hd[u]; i; i = e[i].nt) {
    int v = e[i].to;
    if (!dfn[v]) {
      tarjan(v);
      low[u] = min(low[u], low[v]);
      if (low[v] >= dfn[u]) {
        if (++f > 1 || u != root) cut[u] = true;
        cnt++;
        do dcc[cnt].push_back(sta[top--]);
        while (sta[top + 1] != v);
        dcc[cnt].push_back(u);
      }
    } else
      low[u] = min(low[u], dfn[v]);
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  int u, v;
  for (int i = 1; i <= m; i++) {
    cin >> u >> v;
    if (u != v) uadd(u, v);
  }
  for (int i = 1; i <= n; i++)
    if (!dfn[i]) root = i, tarjan(i);
  cout << cnt << '\n';
  for (int i = 1; i <= cnt; i++) {
    cout << dcc[i].size() << ' ';
    for (int j = 0; j < dcc[i].size(); j++) cout << dcc[i][j] << ' ';
    cout << '\n';
  }
  return 0;
}

文章写完了\ 把板子切了啊啊啊啊啊啊！\ **写完了都没切掉，***

强连通分量

注意: 文中关于Tarjan算法的具体内容出现过很多次，一处看不懂没关系，直接跳都可以，尤其是Tajan会反复说明、重申、补充

强连通分量 (概念)

可以看这个 blog

wiki: 强连通的定义是：有向图 G 强连通是指，G 中任意两个结点连通

说人话：

强连通图：

若从顶点 v 到 m 有路径，则称这俩顶点时强连通的。若任意一对顶点都是强连通的，称此图为强连通图

其实就是 u 可以到 v,v 也可以到 u (因为是无向图嘛)

强连通分量(SCC)：

有向图中的极大强连通子图称为有向图的强连通分量

就是在有向图中去找一个极大的子图 G, 且 G 是强连通图，极大就是 额，尽可能的大吧

图中，子图 {1,2,3,4} 为一个强连通分量，因为顶点 1,2,3,4 两两可达。{5},{6} 也分别是两个强连通分量。

P3387 【模板】缩点

这是 tarjan 的板子题

那么来学 tarjan:

DFS 生成树：

我们考虑 DFS 生成树与强连通分量之间的关系：

如果结点 u 是某个强连通分量在搜索树中遇到的第一个结点，那么这个强连通分量的其余结点肯定是在搜索树中以 u 为根的子树中。结点 u 被称为这个强连通分量的根

tarjan 算法逻辑

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

接下来，对于每个节点u,维护2个变量dfn[i]和low[i]

\textit{dfn}_u: dfs时搜索次序

一个结点的子树内结点的 dfn 都大于该结点的 dfn。

从根开始的一条路径上的 dfn 严格递增，low 严格非降。

1.v 未被访问：继续对 v 进行深度搜索。在回溯过程中，用 \textit{low}_v 更新 \textit{low}_u。因为存在从 u 到 v 的直接路径，所以 v 能够回溯到的已经在栈中的结点，u 也一定能够回溯到。

2.v 被访问过，已经在栈中：根据 low 值的定义，用 \textit{dfn}_v 更新 \textit{low}_u。

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

因此，在回溯的过程中，判定 \textit{dfn}_u=\textit{low}_u 是否成立，如果成立，则栈中 u 及其上方的结点构成一个 SCC(强连通分量)。

复杂度O(n+m)

优秀图解BLOG

题面:

参考博客

【模板】缩点

题目描述

输入格式

输出格式

为啥叫缩点呢?

缩点，就是把一张有向有环图中的环缩成一个个点，形成一个有向无环图

此题解法：

这道题的思路比较恶心：tarjan缩点+dp

现在给出一个有向有环图，那么这个图不是一个DAG，所以不能在这种图上做拓扑排序或其他有关DAG的操作了 ps:DAG->有向无环图

可以看出\{1,2,3\}是一个强连通分量

我们的目的首先就是求出所有的强连通分量然后再将其缩成一个点，便可将图转为一个DAG

那么问题就被化简成了确定每个强连通分量的根

然后使用Tarjan求SCC

如果把每个scc看成一个点，则是DAG图，即建出一个新图

对每个点都不断用他的入边的点更新他，取最大值，f[i]表示i点（缩点后）的经过点和最大值

w代表当前点，rdr数组代表w点的入边的点，dis数组是权值。

dp方程: f[w]=max(f[w],f[rdr[w][j-1]]+dis_[w]);

应该是在fz抄的老师的code:

P3388 【模板】割点（割顶）

题目描述

输入格式

输出格式

割点

割点概念，应该很好理解：

在一个无向图中，如果删除某个顶点，这个图就不再连通（任意两点之间无法相互到达），那么这个顶点就是这个图的割点

优秀博客

很容易想到的方法是：依次删除每一个顶点，然后用dfs或者bfs来检查图是否依然连通。如果删除某个顶点后，导致图不再连通，那么刚才删除的顶点就是割点

这种方法的时间复杂度是O(N(N+M)) 暴力你还想咋样

自然是Tarjan

再次贴一遍CODE:

看解释先:

再定义一个数组low来记录每个顶点在不经过父顶点时，能够回到的最小“时间戳”

对于某个顶点u，如果存在至少一个顶点 v（ u 的儿子），使得low[v]>=num[u]，即不能回到祖先，那么u点为割点

具体过程理解可以看这个blog

4 经过搜索后，没有回溯到比父亲 3 时间戳更小的点，low[4] ≥dfn[3] ,所以 3 为割点。

1为根，扫到3 和 7是3 和 7都没访问过，则1有2个子树，即1为割点

7和3一样，满足low[8]>=dfn[7],为割点

每日CTJ：

割边

除了割点还有一种问题是求割边（也称桥），即在一个无向图中删除某条边后，图不再连通

只需将求割点的算法修改一个符号就可以。 只需将low[v]>=num[u]改为low[v]>num[u]。

这是为什么呢？

low[v]和num[u]相等则表示还可以回到父亲结点； 而low[v]>num[u]则表示连父亲都回不到了。倘若顶点v不能回到祖先，也没有另外的路能回到父亲，那么 u-v 这条边就是割边

双连通分量

def定义:

在一张连通的无向图中，对于两个点 u 和 v，如果无论删去哪条边（只能删去一条）都不能使它们不连通，我们就说 u 和 v 边双连通。

在一张连通的无向图中，对于两个点 u 和 v，如果无论删去哪个点（只能删去一个，且不能删 u 和 v 自己）都不能使它们不连通，我们就说 u 和 v 点双连通。

就是在有向图中去找一个极大的子图 G, 且 G 是强连通图，极大就是额，尽可能的大吧

只需将求割点的算法修改一个符号就可以。只需将low[v]>=num[u]改为low[v]>num[u]。

low[v]和num[u]相等则表示还可以回到父亲结点；而low[v]>num[u]则表示连父亲都回不到了。倘若顶点v不能回到祖先，也没有另外的路能回到父亲，那么 u-v 这条边就是割边

对于一个无向图中的极大边双连通的子图，我们称这个子图为一个边双连通分量

对于一个无向图中的极大点双连通的子图，我们称这个子图为一个点双连通分量

用 Tarjan 求双连通分量过程与求强连通分量类似，可以先阅读强连通分量的 Tarjan 算法。