• 浅谈tarjan算法

    塔杨老爷子创造的算法让人头皮发麻，却不得不赞叹他的过人之处----前言

    学习tarjan之前我们需要知道一些图论的前置知识

    前置知识

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

    强连通分量（Strongly Connected Components，SCC）的定义是：极大的强连通子图。

    还有DFS树、DFS序等请前往此处学习，这里不再赘述

    tarjan之求强连通分量

    首先先来说明一下每个数组的作用

    vis[]判断该点是否在栈里

    used[]判断该点是否遍历到

    dfn[]该点被搜索到的次序编号（时间戳），不难发现每个点的时间戳都不一样

    low[]在该点的子树中能够回溯到的最早的已经在栈中的结点

    num[]记录每个强连通分量里含有多少个点

    color[]记录该点在哪个强连通分量中

    G[][]当然是我最爱的vector存图方式啦（链式前向星，达咩！）

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

    学习算法怎么能不配合点例题呢

    [USACO06JAN]The Cow Prom S - 洛谷

    这个题题意很容易，一张有向图里求强连通分量大于1的个数，tarjan的基本操作

    该题样例

     从这张图中我们不难看出，点集{1,2,4}是一个强连通分量，因为点集中的点两两可以互相到达，而{3}和{5}是两个独立的强连通分量，下面我们通过这个样例来说一下tarjan求强连通分量的过程

    首先我们是从点1开始进行tarjan算法，然后点1入栈，开始遍历点2，发现点2并不在栈中，那么就开始遍历点2，又发现点4不在栈中，

    那么开始遍历点4，发现点1已经入栈，low[4]=min(low[4],dfn[1])，然后low[4]与dfn[4]不相同，

    然后再回溯点2，执行下一行代码，low[2]=min(low[2],low[4]),发现low[2]与dfn[2]也不相同，再回溯点1，low[1]=min(low[1],low[2]),然后此时发现low[1]与dfn[1]相同，说明已经到根，然后就开始对点染色和强连通分量的计算，以及其中点的个数的计算，然后结束这一轮的tarjan算法，发现点3并没有遍历过，再从点3开始重复上述操作

    AC代码：

    1. #include 
    2. using namespace std;
    3. using LL = long long;
    4. int main() {
    5.     ios::sync_with_stdio(false);
    6.     cin.tie(nullptr);
    7.     int n, m, ans = 0, idx = 0, cnt = 0;
    8.     cin >> n >> m;
    9.     stack<int> st;
    10.     vector<int> vis(n + 1), used(n + 1), dfn(n + 1), low(n + 1), num(n + 1), color(n + 1);
    11.     vectorint>> G(n + 1);
    12.     for (int i = 0; i < m; i++) {
    13.         int u, v;
    14.         cin >> u >> v;
    15.         G[u].push_back(v);
    16.     }
    17.     function<void(int)> tarjan = [&](int u) {
    18.         dfn[u] = low[u] = ++idx;
    19.         st.push(u);
    20.         vis[u] = used[u] = true;
    21.         for (auto v : G[u]) {
    22.             if (!dfn[v]) {
    23.                 tarjan(v);
    24.                 low[u] = min(low[u], low[v]);
    25.             }
    26.             else if (vis[v]) {
    27.                 low[u] = min(low[u], dfn[v]);
    28.             }
    29.         }
    30.         if (dfn[u] == low[u]) {
    31.             int z;
    32.             cnt++;
    33.             do {
    34.                 z = st.top();
    35.                 st.pop();
    36.                 color[z] = cnt;
    37.                 num[cnt]++;
    38.                 vis[z] = false;
    39.             } while (z != u);
    40.         }
    41.     };
    42.     for (int i = 1; i <= n; i++) {
    43.         if (!used[i]) {
    44.             tarjan(i);
    45.         }
    46.     }
    47.     for (int i = 1; i <= cnt; i++) {
    48.         if (num[i] > 1) {
    49.             ans++;
    50.         }
    51.     }
    52.     cout << ans << '\n';
    53.     return 0;
    54. }

    tarjan之求缩点

    求缩点其实就是建立在前面求强连通分量的基础之上，对将每一个环看成一个点，我们在用tarjan求强连通分量的时候也记录了每个点所在的强连通分量(类似染色)，以及每个强连通分量里有多少个点，因此，为了缩点，我们需要遍历每一条边，如果u和v处于不同的强连通分量里，那么说明这两个强连通分量之间有一条有向边，那么我们就把两个强连通分量看成两个不同的点，然后按照建图方式建图就好了（听君一席话，如听一席话）

    [USACO03FALL / HAOI2006] 受欢迎的牛 G - 洛谷


     

    题目的意思是牛A能当明星牛，当且仅当所有牛都喜欢他，而且牛对牛的喜欢可以传递，这就相当于一张由有向边构成的有向图，我们要先求出所有强连通分量来，然后进行缩点，如果缩点以后有出度为0的，那么这个点就有可能是一个或一群明星牛，为什么说可能呢，因为如果出度为0的点大于1个的话，也就是说这些出度为0的点之间是不连通的，那么也就不符合所有牛都喜欢的定义，注意，这个点指的是缩完以后的点，并不是最初定义的编号1-n的点

    AC代码：

    1. #include 
    2. using namespace std;
    3. using LL = long long;
    4. int main() {
    5.     ios::sync_with_stdio(false);
    6.     cin.tie(nullptr);
    7.     int n, m, ans = 0, idx = 0, cnt = 0;
    8.     cin >> n >> m;
    9.     stack<int> st;
    10.     vector<int> du(n + 1), vis(n + 1), used(n + 1), dfn(n + 1), low(n + 1), num(n + 1), color(n + 1);
    11.     vectorint>> G(n + 1);
    12.     for (int i = 0; i < m; i++) {
    13.         int u, v;
    14.         cin >> u >> v;
    15.         G[u].push_back(v);
    16.     }
    17.     function<void(int)> tarjan = [&](int u) {
    18.         dfn[u] = low[u] = ++idx;
    19.         st.push(u);
    20.         vis[u] = used[u] = true;
    21.         for (auto v : G[u]) {
    22.             if (!dfn[v]) {
    23.                 tarjan(v);
    24.                 low[u] = min(low[u], low[v]);
    25.             }
    26.             else if (vis[v]) {
    27.                 low[u] = min(low[u], dfn[v]);
    28.             }
    29.         }
    30.         if (dfn[u] == low[u]) {
    31.             int z;
    32.             cnt++;
    33.             do {
    34.                 z = st.top();
    35.                 st.pop();
    36.                 color[z] = cnt;
    37.                 num[cnt]++;
    38.                 vis[z] = false;
    39.             } while (z != u);
    40.         }
    41.     };
    42.     for (int i = 1; i <= n; i++) {
    43.         if (!used[i]) {
    44.             tarjan(i);
    45.         }
    46.     }
    47.     for (int i = 1; i <= n; i++) {
    48.         for (auto v : G[i]) {
    49.             if (color[i] != color[v]) {
    50.                 du[color[i]]++;
    51.             }
    52.         }
    53.     }
    54.     for (int i = 1; i <= cnt; i++) {
    55.         if (du[i] == 0) {
    56.             ans++;
    57.         }
    58.     }
    59.     if (ans > 1 or ans == 0) {
    60.         cout << "0\n";
    61.     }
    62.     else {
    63.         cout << num[ans] << '\n';
    64.     }
    65.     return 0;
    66. }

    讲解缩点怎么会没有洛谷的真·模板题呢？

    【模板】缩点 - 洛谷

    题意是一张有向图，可以走一个点或者一条边任意遍，然后求一条路径上的最大值

    做法

    我们可以先用tarjan求出强连通分量，注意求强连通分量的时候把该强连通分量里面的点权也顺便求出来，这样便于求缩完点以后的点权，然后再进行缩点，建图，之后就是对于一般有向图的拓扑排序DP求最大值（感觉代码写的并不是很漂亮QAQ，能力有限）

    AC代码：

    1. #include 
    2. using namespace std;
    3. using LL = long long;
    4. int main() {
    5.     ios::sync_with_stdio(false);
    6.     cin.tie(nullptr);
    7.     int n, m, idx = 0, cnt = 0;
    8.     cin >> n >> m;
    9.     stack<int> st;
    10.     vector<int> a(n + 1), in(n + 1), val(n + 1), vis(n + 1), used(n + 1), dfn(n + 1), low(n + 1), num(n + 1), color(n + 1);
    11.     vectorint>> G(n + 1), G1(n + 1);
    12.     for (int i = 1; i <= n; i++) {
    13.         cin >> a[i];
    14.     }
    15.     for (int i = 0; i < m; i++) {
    16.         int u, v;
    17.         cin >> u >> v;
    18.         G[u].push_back(v);
    19.     }
    20.     function<void(int)> tarjan = [&](int u) {
    21.         dfn[u] = low[u] = ++idx;
    22.         st.push(u);
    23.         vis[u] = used[u] = true;
    24.         for (auto v : G[u]) {
    25.             if (!dfn[v]) {
    26.                 tarjan(v);
    27.                 low[u] = min(low[u], low[v]);
    28.             }
    29.             else if (vis[v]) {
    30.                 low[u] = min(low[u], dfn[v]);
    31.             }
    32.         }
    33.         if (dfn[u] == low[u]) {
    34.             int z;
    35.             cnt++;
    36.             do {
    37.                 z = st.top();
    38.                 st.pop();
    39.                 color[z] = cnt;
    40.                 num[cnt]++;
    41.                 val[cnt] += a[z];
    42.                 vis[z] = false;
    43.             } while (z != u);
    44.         }
    45.     };
    46.     for (int i = 1; i <= n; i++) {
    47.         if (!used[i]) {
    48.             tarjan(i);
    49.         }
    50.     }
    51.     for (int i = 1; i <= n; i++) {
    52.         for (auto v : G[i]) {
    53.             if (color[i] != color[v]) {
    54.                 G1[color[i]].push_back(color[v]);
    55.                 in[color[v]]++;
    56.             }
    57.         }
    58.     }
    59.     queue<int> qu;
    60.     vector<int> ans(cnt + 1);
    61.     for (int i = 1; i <= cnt; i++) {
    62.         if (in[i] == 0) {
    63.             qu.push(i);
    64.         }
    65.     }
    66.     while (!qu.empty()) {
    67.         int u = qu.front();
    68.         qu.pop();
    69.         ans[u] += val[u];
    70.         for (auto v : G1[u]) {
    71.             in[v]--;
    72.             if (in[v] == 0) {
    73.                 qu.push(v);
    74.                 ans[v] += ans[u];
    75.             }
    76.         }
    77.     }
    78.     cout << *max_element(ans.begin(), ans.end()) << '\n';
    79.     return 0;
    80. }

    tarjan之求割点(割顶)

    先说一下割点的概念

    在无向连通图中，如果将其中一个点以及所有连接该点的边去掉，图就不再连通，那么这个点就叫做割点。

    从这张图上来分析一下哪些点是割点，根据定义，我们可以知道，其中0和3是割点，当去掉其中任意一个或者全部的点所连的边的话，剩下的图就不再连通， 从直观角度来看，如果一个点拥有两颗及以上子树的话，这个点就一定是一个割点，因为两颗子树能互相到达当且仅当经过这个点，当然这是对根节点而言，那么对于非根节点该如何判断其是否是割点？

    这个时候就要%一下塔杨老爷子，tarjan算法巧妙地解决了这个问题，就是使用其中的low[]和dfn[]，dfn[u]表示顶点u第几个被首次访问，low[u]表示顶点u及其子树中的点，通过非父子边，能够回溯到的最早的点（dfn最小）的dfn值，对于边(u, v)，如果low[v]>=dfn[u]，此时u就是割点，

    或者说对一个连通图进行DFS,在DFS的过程中如果存在一个非根点不存在返祖边(不能回到父节点之前的点)，则该节点的父节点便为割点

    附上模板题

    【模板】割点（割顶） - 洛谷

    AC代码：

    1. #include 
    2. using namespace std;
    3. using LL = long long;
    4. int main() {
    5.     ios::sync_with_stdio(false);
    6.     cin.tie(nullptr);
    7.     int n, m, idx = 0, cnt = 0;
    8.     cin >> n >> m;
    9.     vectorint>> G(n + 1);
    10.     for (int i = 0; i < m; i++) {
    11.         int u, v;
    12.         cin >> u >> v;
    13.         G[u].push_back(v);
    14.         G[v].push_back(u);
    15.     }
    16.     vector<bool> cut(n + 1);
    17.     vector<int> dfn(n + 1), low(n + 1);
    18.     function<void(int, int)> tarjan = [&](int u, int fa) {
    19.         dfn[u] = low[u] = ++idx;
    20.         int child = 0;
    21.         for (auto v : G[u]) {
    22.             if (!dfn[v]) {
    23.                 tarjan(v, u);
    24.                 low[u] = min(low[u], low[v]);
    25.                 if (low[v] >= dfn[u] and u != fa) {
    26.                     cut[u] = true;
    27.                 }
    28.                 if (u == fa) {
    29.                     child++;
    30.                 }
    31.             }
    32.             else if (u != fa) {
    33.                 low[u] = min(low[u], dfn[v]);
    34.             }
    35.         }
    36.         if (child >= 2 and u == fa) {
    37.             cut[u] = true;
    38.         }
    39.     };
    40.     for (int i = 1; i <= n; i++) {
    41.         if (!dfn[i]) {
    42.             tarjan(i, i);
    43.         }
    44.     }
    45.     int tot = 0;
    46.     for (int i = 1; i <= n; i++) {
    47.         if (cut[i]) {
    48.             tot++;
    49.         }
    50.     }
    51.     cout << tot << '\n';
    52.     for (int i = 1; i <= n; i++) {
    53.         if (cut[i]) {
    54.             cout << i << " ";
    55.         }
    56.     }
    57.     cout << '\n';
    58.     return 0;
    59. }

    tarjan之点双连通分量

    老规矩，先来介绍一下点双连通分量的一些概念

    点双连通分量---v-DCC

    双连通分量---DCC

    边双连通分量---e-DCC

    点双连通：若对于一个无向图，其任意一个节点对于这个图本身而言都不是割点，则称其点双连通。也就是说，删除任意点及其相关边后，整个图仍然属于一个连通分量。

    点双连通分量：无向图中，极大的点双连通子图。与连通分量类似，抽离出一些点及它们之间的边，使得抽离出的图是一个点双连通图，在这个前提下，使得抽离出的图越大越好。

    一张无向连通图是点双连通图当且仅当满足下列两个条件之一：

    1.图的顶点不超过2

    2.(当图的顶点大于2)图中任意两点都同时包含在至少一个简单环中，其中简单环指的是不自交的环(即自环)

    点双连通分量不具有传递性，例如下图

     可知1和4点双连通，4和7点双连通，但1和7点双不连通，因为删掉4及其连接的边，1和7将不再连通

    为了求出点双连通分量，需要在tarjan过程中维护一个栈，用栈去维护一个点双连通分量中的所有点，维护方法：

    1.当一个节点第一次被访问时，把该节点入栈

    2.当割点判定法则中的条件dfn[u]<=low[v]成立时，无论u是否为根，都要：

    1)从栈顶不断弹出节点，直至节点v被弹出

    2)刚才弹出的所有节点与节点u一起构成一个点双连通分量

    注意

    <点双连通分量是一个极其容易误解的概念，它与“删除割点后图中剩余的连通块”的概念是不一样的>

    献上模板题

    【模板】点双连通分量 - 洛谷

    AC代码：

    1. #include 
    2. using namespace std;
    3. using LL = long long;
    4. int main() {
    5.     ios::sync_with_stdio(false);
    6.     cin.tie(nullptr);
    7.     int n, m, idx = 0, bcc = 0;
    8.     cin >> n >> m;
    9.     vectorint>> G(n + 1);
    10.     vectorint>> ans(n + 1);
    11.     for (int i = 0; i < m; i++) {
    12.         int u, v;
    13.         cin >> u >> v;
    14.         G[u].push_back(v);
    15.         G[v].push_back(u);
    16.     }
    17.     stack<int> st;
    18.     vector<int> dfn(n + 1), low(n + 1);
    19.     function<void(int, int)> tarjan = [&](int u, int fa) {
    20.         low[u] = dfn[u] = ++idx;
    21.         int son = 0;
    22.         st.push(u);
    23.         for (auto v : G[u]) {
    24.             if (!dfn[v]) {
    25.                 son++;
    26.                 tarjan(v, u);
    27.                 low[u] = min(low[u], low[v]);
    28.                 if (low[v] >= dfn[u]) {
    29.                     bcc++;
    30.                     int z;
    31.                     do {
    32.                         z = st.top();
    33.                         ans[bcc].push_back(z);
    34.                         st.pop();
    35.                     } while (z != v);
    36.                     ans[bcc].push_back(u);
    37.                 }
    38.             } else if (v != fa) {
    39.                 low[u] = min(low[u], dfn[v]);
    40.             }
    41.         }
    42.         if (fa == 0 and son == 0) {
    43.             ans[++bcc].push_back(u);
    44.         }
    45.     };
    46.     for (int i = 1; i <= n; i++) {
    47.         if (!dfn[i]) {
    48.             tarjan(i, 0);
    49.         }
    50.     }
    51.     cout << bcc << '\n';
    52.     for (int i = 1; i <= bcc; i++) {
    53.         cout << ans[i].size() << " ";
    54.         for (auto j : ans[i]) {
    55.             cout << j << " ";
    56.         }
    57.         cout << '\n';
    58.     }
    59.     return 0;
    60. }

    tarjan之求割边(桥)

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

    整体思路和求割点类似，只需要在求割点的代码里改一点点就可以，用链式前向星存图，这里用到一个链式前向星的技巧，有一条边直接连接i号点的前一个点可以直接用i^1得出，且cnt从2开始存才能满足成对变换（位运算特征）

    链式前向星存图：

    1. struct edge {
    2.     int to, nxt;
    3. }e[题目边数的两倍以上];
    4. int cnt = 1, head[题目点数];
    5. void add(int u, int v) {
    6.     e[++cnt].to = v;
    7.     e[cnt].nxt = head[u];
    8.     head[u] = cnt;
    9. }
    10. main() {
    11.     int u, v;
    12.     cin >> u >> v;
    13.     add(u, v);
    14.     add(v, u);//无向图
    15. }

    tarjan求割边

    1. void tarjan(int u, int fa) {
    2.     dfn[u] = low[u] = ++idx;
    3.     for (int i = head[u]; i; i = e[i].nxt) {
    4.         int v = e[i].to;
    5.         if (v == fa) {
    6.             continue;
    7.         }
    8.         if (!dfn[v]) {
    9.             tarjan(v, u);
    10.             low[u] = min(low[u], low[v]);
    11.             if (low[v] > dfn[u]) {
    12.                 bridge++;//桥的个数++
    13.                 e[i].vis = e[i ^ 1].vis = true;//在存边的结构体里再维护一个vis，
    14.                                                   //表示两点之间的边是否是桥
    15.             }
    16.         } else {
    17.             low[u] = min(low[u], dfn[v]);
    18.         }
    19.     }
    20. }

    统计哪些是桥

    1. vectorint,int>> v;
    2. for(int i = 0; i <= cnt; i += 2) {//cnt边的个数
    3.     if (e[i].vis) {//判断是否是桥
    4.         if (e[i].to < e[i ^ 1].to) {//点号小的在前
    5.             v.push_back(make_pair(e[i].to, e[i ^ 1].to));
    6.         }            
    7.         else {
    8.             v.push_back(make_pair(e[i ^ 1].to, e[i].to));
    9.         }        
    10.     }
    11. }

    洛谷竟然没有模板题QAQ，那只好直接过渡到求解边双连通分量了

    tarjan之边双连通分量

    概念

    若一张无向连通图不存在桥（割边），则称它为“边双连通图”。

    无向图的极大边双联通子图被称为“边双联通分量”，简记为“e-DCC”。

    一张无向连通图是边双连通图，当且仅当任意一条边都包含在至少一个简单环中

    做法

    只需求出无向图中所有的桥，把桥都删除后，无向图会分成若干个连通块，每一个联通块都是一个“边双连通分量”。

    在具体的程序实现中，一般先用 Tarjan 算法标记出所有的桥边。然后，再对整个无向图执行一次深度优先遍历（遍历的过程中不访问桥边），划分出每个连通块。

    【模板】边双连通分量 - 洛谷

    AC代码：

    1. #include 
    2. using namespace std;
    3. using LL = long long;
    4. struct edge {
    5.     int to, nxt;
    6.     bool vis;
    7. };
    8. int main() {
    9.     ios::sync_with_stdio(false);
    10.     cin.tie(nullptr);
    11.     int n, m, cnt = 1, idx = 0, dcc = 0;
    12.     cin >> n >> m;
    13.     vector<int> head(n + 1);
    14.     vector e(m * 2 + 2);
    15.     function<void(int, int)> add = [&](int u, int v) {
    16.         e[++cnt].to = v;
    17.         e[cnt].nxt = head[u];
    18.         e[cnt].vis = false;
    19.         head[u] = cnt;
    20.     };
    21.     for (int i = 0; i < m; i++) {
    22.         int u, v;
    23.         cin >> u >> v;
    24.         add(u, v);
    25.         add(v, u);
    26.     }
    27.     vector<int> dfn(n + 1), low(n + 1);
    28.     function<void(int, int)> tarjan = [&](int u, int fa) {
    29.         dfn[u] = low[u] = ++idx;
    30.         for (int i = head[u]; i; i = e[i].nxt) {
    31.             int v = e[i].to;
    32.             if (!dfn[v]) {
    33.                 tarjan(v, i);
    34.                 low[u] = min(low[u], low[v]);
    35.                 if (low[v] > dfn[u]) {
    36.                     e[i].vis = e[i ^ 1].vis = true;
    37.                 }
    38.             } else if (i != (fa ^ 1)) {
    39.                 low[u] = min(low[u], dfn[v]);
    40.             }
    41.         }
    42.     };
    43.     for (int i = 1; i <= n; i++) {
    44.         if (!dfn[i]) {
    45.             tarjan(i, i);
    46.         }
    47.     }
    48.     vector<bool> vis(n + 1);
    49.     vectorint>> ans(n + 1);
    50.     function<void(int)> dfs = [&](int u) {
    51.         vis[u] = true;
    52.         if (u) {
    53.             ans[dcc].push_back(u);
    54.         }
    55.         for (int i = head[u]; i; i = e[i].nxt) {
    56.             int v = e[i].to;
    57.             if (vis[v] or e[i].vis) {
    58.                 continue;
    59.             }
    60.             dfs(v);
    61.         }
    62.     };
    63.     for (int i = 1; i <= n; i++) {
    64.         if (!vis[i]) {
    65.             dcc++;
    66.             dfs(i);
    67.         }
    68.     }
    69.     cout << dcc << '\n';
    70.     for (int i = 1; i <= dcc; i++) {
    71.         cout << ans[i].size() << " ";
    72.         for (auto j : ans[i]) {
    73.             cout << j << " ";
    74.         }
    75.         cout << '\n';
    76.     }
    77.     return 0;
    78. }

    完结！撒花！

  • 相关阅读:
    如何配置固定TCP公网地址实现远程访问内网MongoDB数据库
    Elasticsearch - Elasticsearch集群Cluster（三）
    山西828 B2B企业节进行时 华为携手合作伙伴共探数字化转型
    Hadoop----Hive的使用
    非零基础自学Java (老师：韩顺平) 第8章 面向对象编程(中级部分) 8.9 super关键字
    【jackson解析复杂对象】
    Java运算符详解
    申请400电话的详细步骤及操作指南
    电商直播产业在成都直播基地加速成势 落地天府兴隆湖！
    Stream常用操作以及原理探索
  • 原文地址：https://blog.csdn.net/eyuhaobanga/article/details/126610862