精华内容
下载资源
问答
  • tarjan算法
    2022-06-02 20:29:46

    Tarjan算法

    1 算法简介

    还记得无向图判连通块吗?对于无向图中,判连通块是一件很容易的事。你只需要dfs(深度优先搜索)一下就可以了。但是,如果我们把无向图换成有向图呢?

    这就是另一个故事了…

    2 算法定义

    Robert Tarjan计算机科学家,以LCA,Tarjan等算法闻名。Tarjan是求强连通分量的一个强力的算法。

    要理解Tarjan这个算法,我们先讲几个定义:

    强连通分量 :

    对于一个分量,若任意两个点相通,则称为强连通分量。

    树边 :

    对于一个图的dfs树,它的树边便是此图的树边。

    返祖边 :

    对于一个图的dfs树,可以使得儿子节点返回到它的祖先的边为返祖边。

    横插边 :

    对于一个图的dfs树,可以使得一个节点到达另一个节点且它们互不是祖先的边为横插边。

    神奇海螺结束!

    3 算法详细

    先讲一下我们要用到的数组。

    • dfn:第 i i i个节点他的时间戳

    • low:第 i i i个节点他最多经过一条返祖边所能到达的最小时间戳

    • st:一个栈,用来储存当前还未确定但已经扩展过的点

    • co:第 i i i个节点他所在的强连通分量编号

    我们讲一下算法流程。

    1. 此时来到了点 u u u

    2. 扩展他的子节点,这里假设现在到的子节点为 v v v,扩展完了就来到第 5 5 5

    3. 三种情况:

      • !dfn[v],即还未扩展的点,则我们直接来到第 4 4 4
      • !co[v]&& dfn[v],即还未出栈但已扩展过的点(就是返祖/横叉了嘛),我们更新一下 l o w u = min ⁡ ( l o w u , d f n v ) low_u = \min(low_u, dfn_v) lowu=min(lowu,dfnv),并返回第 2 2 2步。(看不懂的感性理解一下)
      • co[v] && dfn[v],即已出栈且遍历过,那么我们直接返回第 2 2 2
    4. 我们先对 v v v这个顶点扩展一下(即返回第 1 1 1步),然后把 l o w u = min ⁡ ( l o w u , l o w v ) low_u = \min(low_u, low_v) lowu=min(lowu,lowv)更新一下,接着回到第 2 2 2

    5. 如果 d f n u = l o w u dfn_u = low_u dfnu=lowu,这说明 u u u没有返祖边,它拥有属于自己的一棵子树,而此时栈中的点又一定能到 u u u(要不然就被弹掉了),所以此时我们只需要弹栈就可以了!

    6. 我们已经完成了所有操作,可以回溯到第 1 1 1步了

    4 模板代码

    先放一道模板题 : CF427C Checkposts

    这题是一道赤裸裸的强连通分量,晾一下代码。

    # include <bits/stdc++.h>
    using namespace std;
    
    # define ll long long
    # define lf double
    # define GO(i,a,b) for(int i = a; i <= b; i ++)
    # define RO(i,b,a) for(int i = b; i >= a; i --)
    # define FO(i,u,head,e) for(int i = head[u]; i; i = e[i].next)
    # define CI const int
    # define pii pair<int,int>
    # define MP(a,b) make_pair(a,b)
    # define PB(x) push_back(x)
    # define mem(a,x) memset(a, x, sizeof a)
    # define F first
    # define S second
    
    CI maxn = 1e5 + 7;
    CI maxm = 3e5 + 7;
    CI mod = 1e9 + 7;
    
    int n, m;
    
    struct Edge{
    	int u, v, next;
    }e[maxm];
    
    int head[maxn], cnt;
    
    void add(int u, int v){
    	e[++ cnt].u = u;
    	e[cnt].v = v;
    	e[cnt].next = head[u];
    	head[u] = cnt;
    }
    
    int dfn[maxn];
    int low[maxn];
    int vis[maxn]; // 0未访问, 1在栈中, 2已访问 
    int tar[maxn]; // 连通分量 
    int col;
    
    int tmp;
    
    stack <int> q;
    
    void Tarjan(int u){
    	q.push(u);
    	vis[u] = 1; // 在栈中 
    	low[u] = dfn[u] = ++ tmp;
    	FO (i, u, head, e){
    		int v = e[i].v;
    		if (vis[v] == 2)
    			continue;
    		if (dfn[v])
    			low[u] = min <int> (low[u], dfn[v]);
    		else{
    			Tarjan(v);
    			low[u] = min <int> (low[u], low[v]);
    		}
    	}
    	if (dfn[u] == low[u]){
    		int v = q.top();
    		q.pop();
    		col ++;
    		while (!q.empty() && v != u){
    			vis[v] = 2;
    			tar[v] = col;
    			v = q.top();
    			q.pop();
    			
    		}
    		vis[u] = 2;
    		tar[u] = col;
    	}
    }
    
    vector <int> poi[maxn];
    
    ll a[maxn];
    
    int main(){
    	cin >> n;
    	GO (i, 1, n)
    		scanf("%lld", &a[i]);
    	cin >> m;
    	GO (i, 1, m){
    		int u, v;
    		scanf("%d %d", &u, &v);
    		add(u, v);
    	}
    	
    	GO (i, 1, n)
    		if (!vis[i])
    			Tarjan(i);
    	
    	GO (i, 1, n)
    		poi[tar[i]].PB(i);
    	
    	ll ans1 = 1, ans2 = 0;
    	GO (i, 1, col){
    		ll minn = 2e18;
    		ll res = 0;
    		for (int j : poi[i])
    			minn = min <ll> (minn, a[j]);
    		for (int j : poi[i])
    			if (a[j] == minn)
    				res ++;
    		ans2 += minn;
    		ans1 = (ans1 * res) % mod;
    	} 
    	
    	printf("%lld %lld", ans2, ans1);
    	return 0;
    }
    
    更多相关内容
  • Tarjan算法讲义

    2020-07-14 14:04:24
    Tarjan 算法是图论中非常实用 / 常用的算法之一,能解决强连通分量,双连通分量,割点和桥,求最近公共祖先(LCA)等问题。 关于 Tarjan 算法,笔者将用一系列文章系统介绍 Tarjan 算法的原理以及其主要解决的问题...
  • Tarjan算法精讲

    2016-05-07 18:03:15
    更精细的追踪每一个步骤,力求完全剖析算法
  • Tarjan 算法论文 DEPTH-FIRST SEARCH AND LINEAR GRAPH ALGORITHMS.pdf
  • (图论) Tarjan 算法

    2022-06-14 19:46:16
    Tarjan 算法是图论中非常著名和常用的算法之一,能解决最近公共祖先(LCA),强连通分量,割点和割边(桥),双连通分量等问题。Tarjan 是基于dfs搜索的算法,依据递归栈,时间戳等信息能解决多种问题。在dfs中每个点...

    前言

    Tarjan 算法是图论中非常著名和常用的算法之一,能解决最近公共祖先(LCA),强连通分量,割点和割边(桥),双连通分量等问题。

    Tarjan 是基于dfs搜索的算法,依据递归栈,时间戳等信息能解决多种问题。在dfs中每个点只递归一次,边也只利用一次,因此时间复杂度为 O ( n + m ) {O(n+m)} O(n+m)

    本文主要以记录模板为主,不做详细教学,需要读者有一定的dfs基础,希望读者能总结出属于自己的模板。

    在求强联通分量处,给出了另一种kosaraju算法的模板。

    本文并没有求双联通分量的模板,以后有机会会给出。

    img

    最近公共祖先 (LCA)

    LCA - Lowest Common Ancestors

    • 建树的边 (双向)
    • 建查询的边 (双向)
    • dfs
      • 入 vis 遍历子节点dfs
      • 回 并查集nex存cur
      • 离 枚举查询组 借助并查集的路径压缩

    视频讲解:

    322 最近公共祖先 Tarjan算法_哔哩哔哩_bilibili

    练习题:

    洛谷:P3379 【模板】最近公共祖先(LCA)

    // P3379 【模板】最近公共祖先(LCA)
    #include <bits/stdc++.h>
    using namespace std;
    
    const int M = 10 + 500000;
    vector<vector<int>> graph(M);             // 存图(树)
    vector<vector<pair<int, int>>> query(M);  // 询问
    
    int father[M];  // 并查集
    bool vis[M];    // vis
    int ans[M];     // 第几组询问的答案
    
    void initUnionFind(int n) {
        for (int i = 0; i <= n; i++) {
            father[i] = i;
        }
    }
    // 必须路径压缩
    int unionFind(int x) {
        return x == father[x] ? x : father[x] = unionFind(father[x]);
    }
    // Tarjan 算法
    void Tarjan(int cur) {
        // dfs 入
        vis[cur] = true;
        for (int& nex : graph[cur]) {
            if (!vis[nex]) {
                Tarjan(nex);
                // dfs 回
                father[nex] = cur;
            }
        }
    
        // dfs 离开
        for (auto& it : query[cur]) {
            int &to = it.first, &idx = it.second;
            // 若访问过,则可以记录
            if (vis[to]) {
                ans[idx] = unionFind(to);
            }
        }
    }
    
    int main() {
        // 边数 询问数 根节点
        int n, m, root;
        scanf("%d %d %d", &n, &m, &root);
        initUnionFind(n);
    
        // 存无向图
        for (int i = 1, a, b; i <= n - 1; i++) {
            scanf("%d %d", &a, &b);
            graph[a].emplace_back(b);
            graph[b].emplace_back(a);
        }
    
        // 询问 也要双向存
        for (int i = 1, a, b; i <= m; i++) {
            scanf("%d %d", &a, &b);
            query[a].emplace_back(b, i);
            query[b].emplace_back(a, i);
        }
    
        Tarjan(root);
    
        for (int i = 1; i <= m; i++) {
            printf("%d\n", ans[i]);
        }
    
        return 0;
    }
    

    强连通分量

    tarjan

    视频讲解:

    算法轻松掌握tarjan强连通分量_哔哩哔哩_bilibili

    思想:

    在递归站中的low值相等的点是一个强联通分量

    dfn值和low值相等的是该分量的代表点

    练习题:

    杭电:迷宫城堡 - 1269

    洛谷:P3387 【模板】缩点

    /**
     * https://www.luogu.com.cn/problem/P3387
     * P3387 【模板】缩点
     *
     * tarjan 求强连通分量
     * 然后缩点构造DAG图
     */
    #include <bits/stdc++.h>
    #define int long long
    using namespace std;
    
    // tarjan 标配
    vector<vector<int>> graph;  // 存图
    vector<int> dfn;            // dfs被访问的时间点
    vector<int> low;            // 通过回溯可以到达的最早时间点
    int timestamp = 1;          // 时间戳
    // 求强连通分量 标配
    vector<int> scc;     // 强联通分量
    stack<int> stk;      // 递归栈
    vector<bool> inStk;  // 快速辨别是都在递归栈中
    
    void tarjan(int cur) {
        dfn[cur] = low[cur] = timestamp++;
        stk.push(cur);
        inStk[cur] = true;
    
        for (int& nex : graph[cur]) {
            if (dfn[nex] == 0) {
                // 未访问则搜索一次
                tarjan(nex);
                low[cur] = min(low[cur], low[nex]);
            } else if (inStk[nex]) {
                // 在栈中,也要松弛一次
                low[cur] = min(low[cur], dfn[nex]);
            }
        }
    
        // 自己的dfn和low相同,则构成一个强联通分量
        if (dfn[cur] == low[cur]) {
            int x = -1;
            do {
                x = stk.top();
                stk.pop();
                inStk[x] = false;
                scc[x] = cur;
            } while (x != cur);
        }
    }
    
    signed main() {
        int n, m;
        cin >> n >> m;
    
        graph.resize(n + 1);
        dfn.resize(n + 1);
        low.resize(n + 1);
        timestamp = 1;
        scc.resize(n + 1, -1);
        inStk.resize(n + 1);
    
        vector<int> val(n + 1);   // 点权
        vector<int> from(m + 1);  // 出发点
        vector<int> to(m + 1);    // 到达点
    
        // 点权
        for (int i = 1; i <= n; i++) {
            cin >> val[i];
        }
        // 建图,单向图
        for (int i = 1; i <= m; i++) {
            cin >> from[i] >> to[i];
            graph[from[i]].emplace_back(to[i]);
        }
    
        // 跑tarjan 获得强连通分量
        for (int i = 1; i <= n; i++) {
            if (dfn[i] == 0) {
                tarjan(i);
            }
        }
    
        /** ******** tarjan 跑完,获得强连通分量 ****************************/
        /** ******** 根据强连通分量,缩点构造DAG图 ***************************/
    
        // 先将每个强联通分量的点权集中到代表点上
        for (int i = 1; i <= n; i++) {
            if (scc[i] != i) {  // 代表点不用重复加
                val[scc[i]] += val[i];
            }
        }
    
        unordered_map<int, vector<int>> dagGraph;
        for (int i = 1; i <= m; i++) {
            int &u = from[i], &v = to[i];
            // 不在一个分量中
            if (scc[u] != scc[v]) {
                dagGraph[scc[u]].emplace_back(scc[v]);
            }
        }
    
        function<int(int)> dfsDag = [&](int cur) -> int {
            int sum = 0;
            for (int& nex : dagGraph[cur]) {
                // 获得子树的最大值,还可以记忆化优化下
                sum = max(sum, dfsDag(nex));
            }
            return val[cur] + sum;
        };
    
        int maxx = 0;
        // 遍历每个点,可能有某点的是单独的分量没有边
        for (int i = 1; i <= n; i++) {
            if (scc[i] == i) {
                maxx = max(maxx, dfsDag(scc[i]));
            }
        }
    
        cout << maxx << endl;
    
        return 0;
    }
    

    kosaraju

    另一种求强连通分量的方法

    • 建立正向和反向图
    • 先dfs反向图
    • 在正向图中逆序dfs反向图的结果,并记录每个点在哪个联通分量中
    /**
     * https://www.luogu.com.cn/problem/P3387
     * P3387 【模板】缩点
     *
     * kosaraju 求强连通分量
     * 然后缩点构造DAG图
     */
    #include <bits/stdc++.h>
    #define int long long
    using namespace std;
    
    // kosaraju 标配
    vector<vector<int>> forwardGraph;  // 正向图
    vector<vector<int>> reverseGraph;  // 反向图
    vector<int> scc;                   // 强连通分量
    vector<int> vis;                   // vis标记
    stack<int> stk;                    // 反图入栈
    
    void reverseDFS(int cur) {
        vis[cur] = true;
        for (int& nex : reverseGraph[cur]) {
            if (!vis[nex]) {
                reverseDFS(nex);
            }
        }
        // 访问的点依次入栈
        stk.push(cur);
    }
    
    void forwardDFS(int cur, int father) {
        vis[cur] = true;
        scc[cur] = father;  // 记录是哪个强连通分量
        for (int& nex : forwardGraph[cur]) {
            if (!vis[nex]) {
                forwardDFS(nex, father);
            }
        }
    }
    
    signed main() {
        int n, m;
        cin >> n >> m;
    
        forwardGraph.resize(n + 1);
        reverseGraph.resize(n + 1);
        scc.resize(n + 1);
        vis.resize(n + 1);
    
        vector<int> val(n + 1);   // 点权
        vector<int> from(m + 1);  // 出发点
        vector<int> to(m + 1);    // 到达点
    
        // 记录点权
        for (int i = 1; i <= n; i++) {
            cin >> val[i];
        }
    
        // 正向反向图同时建立
        for (int i = 1; i <= m; i++) {
            cin >> from[i] >> to[i];
            forwardGraph[from[i]].push_back(to[i]);
            reverseGraph[to[i]].push_back(from[i]);
        }
    
        fill(vis.begin(), vis.end(), false);
        // 反向图遍历
        for (int i = 1; i <= n; i++) {
            if (!vis[i]) {
                reverseDFS(i);
            }
        }
        fill(vis.begin(), vis.end(), false);
        // 逆序遍历反向图的结果
        // 目的是获得强连通分量scc
        while (!stk.empty()) {
            int cur = stk.top();
            stk.pop();
            if (!vis[cur]) {
                forwardDFS(cur, cur);
            }
        }
    
        /** ************** kosaraju 跑完,获得强连通分量 *********************/
        /** ******** 根据强连通分量,缩点构造DAG图 ***************************/
    
        // 先将每个强联通分量的点权集中到代表点上
        for (int i = 1; i <= n; i++) {
            if (scc[i] != i) {  // 代表点不用重复加
                val[scc[i]] += val[i];
            }
        }
    
        unordered_map<int, vector<int>> dagGraph;
        for (int i = 1; i <= m; i++) {
            int &u = from[i], &v = to[i];
            // 不在一个分量中
            if (scc[u] != scc[v]) {
                dagGraph[scc[u]].emplace_back(scc[v]);
            }
        }
    
        function<int(int)> dfsDag = [&](int cur) -> int {
            int sum = 0;
            for (int& nex : dagGraph[cur]) {
                // 获得子树的最大值,还可以记忆化优化下
                sum = max(sum, dfsDag(nex));
            }
            return val[cur] + sum;
        };
    
        int maxx = 0;
        // 遍历每个点,可能有某点的是单独的分量没有边
        for (int i = 1; i <= n; i++) {
            if (scc[i] == i) {
                maxx = max(maxx, dfsDag(scc[i]));
            }
        }
    
        cout << maxx << endl;
    
        return 0;
    }
    

    割点 割边

    视频讲解:

    算法轻松掌握tarjan割点&桥算法_哔哩哔哩_bilibili

    算法轻松掌握tarjan割点&桥算法_5_code实现_哔哩哔哩_bilibili

    割点:

    • cur != root && cur 有儿子 && low[nex] >= dfn[cur]
    • cur == root && cur 有儿子数量 >= 2

    割边:

    • low[nex] > dfn[cur]

    来自:邋遢大哥233的个人空间_哔哩哔哩_bilibili

    在这里插入图片描述

    割点

    练习题:

    洛谷:P3388 【模板】割点(割顶)

    // P3388 【模板】割点(割顶)
    // 写法挺多的,以后总结出自己的模板
    #include <bits/stdc++.h>
    using namespace std;
    
    const int M = 10 + 2 * 10000;
    
    vector<vector<int>> graph(M);  // 存图
    int dfn[M];                    // dfs被访问的时间点
    int low[M];                    // 通过回溯可以到达的最早时间点
    int father[M];                 // 记录父节点
    bool cut[M];                   // 是否是割点
    
    int timestamp = 1;  // 时间戳
    
    void tarjan(int cur) {
        dfn[cur] = low[cur] = timestamp++;
        int child = 0;
    
        for (auto& nex : graph[cur]) {
            if (dfn[nex] == 0) {
                // 未访问则搜索一次
                child++, father[nex] = cur;
                tarjan(nex);
                // 是根节点,并且孩子个数大于等于2
                if (-1 == father[cur] && child >= 2) {
                    cut[cur] = true;
                }
                // 不是根节点,但是孩子不可以回溯的更高
                if (-1 != father[cur] && low[nex] >= dfn[cur]) {
                    cut[cur] = true;
                }
    
                // // 是割边(桥)
                // if (low[nex] > dfn[cur]) {
                //     // 每条边只会被访问一次,直接存
                //     //
                //     子树的回溯值比当权点的时间戳大于等于,则表示不会回溯到更先的节点,则是割边
                // }
    
                low[cur] = min(low[cur], low[nex]);
            } else if (nex != father[cur]) {
                // 访问过,但是并不是父节点
                low[cur] = min(low[cur], dfn[nex]);
            }
        }
    }
    
    int main() {
        memset(dfn, 0, sizeof(dfn));
        memset(low, 0, sizeof(low));
        memset(father, -1, sizeof(father));
        memset(cut, false, sizeof(cut));
    
        int n, m;
        scanf("%d %d", &n, &m);
    
        // 无向图
        for (int i = 1, from, to; i <= m; i++) {
            scanf("%d %d", &from, &to);
            graph[from].emplace_back(to);
            graph[to].emplace_back(from);
        }
    
        for (int i = 0; i <= n; i++) {
            if (dfn[i] == 0) {
                tarjan(i);
            }
        }
    
        // 统计割点数量
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += cut[i];
        }
        printf("%d\n", sum);
        for (int i = 1; i <= n; i++) {
            if (cut[i]) {
                printf("%d ", i);
            }
        }
    
        return 0;
    }
    

    割边 (桥)

    练习题:

    力扣:1192. 查找集群内的「关键连接」

    class Solution {
    private:
        vector<vector<int>> graph;
        vector<int> dfn;  // 时间戳
        vector<int> low;  // 回溯值
        int timestamp = 1;
    
        vector<vector<int>> ans;
    
        void tarjan(int cur, int pre) {
            dfn[cur] = low[cur] = timestamp++;
    
            for (int& nex : graph[cur]) {
                // 因为是图,防止环
                if (nex == pre) {
                    continue;
                }
                if (dfn[nex] == 0) {
                    // 还未dfs过
                    tarjan(nex, cur);
                    // 子节点回溯不到cur之前
                    // 注意没有=因为可能有环
                    if (low[nex] > dfn[cur]) {
                        ans.emplace_back(vector<int>{cur, nex});
                    }
                    // 利用子节点的回溯值更新
                    low[cur] = min(low[cur], low[nex]);
                } else {
                    // 不是父节点
                    low[cur] = min(low[cur], dfn[nex]);
                }
            }
        }
    
    public:
        vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
            graph.resize(n);
            dfn.resize(n);
            low.resize(n);
    
            // 存无向图
            for (vector<int>& arr : connections) {
                graph[arr[0]].emplace_back(arr[1]);
                graph[arr[1]].emplace_back(arr[0]);
            }
    
            for (int i = 0; i < n; i++) {
                if (dfn[i] == 0) {
                    tarjan(i, -1);
                }
            }
    
            return ans;
        }
    };
    

    其他相关资料

    60 分钟搞定图论中的 Tarjan 算法(一) - 知乎 (zhihu.com)

    tarjan算法_百度百科 (baidu.com)

    END

    展开全文
  • tarjan算法呕心沥血之作,动画演示,步步清晰可见,详细的描述了tarjan算法的工作过程,比网上的单纯的图片更加容易理解。
  • Tarjan算法详解

    2022-05-11 15:52:48
    tarjan强连通分量算法 1. 概念 连通:无向图中,从任意点i可到达任一点j 强连通:有向图中,从任意点i可到达任一点j 弱连通:把有向图看作无向图时,从任意点i可到达任一点j 如图,强连通无论那个点,都能按照方向...

    一、什么是强连通分量

    tarjan强连通分量算法

    1. 概念

    连通:无向图中,从任意点i可到达任一点j

    强连通:有向图中,从任意点i可到达任一点j

    弱连通:把有向图看作无向图时,从任意点i可到达任一点j
    在这里插入图片描述

    • 如图,强连通无论那个点,都能按照方向到达任意一点,弱连通如果强行按方向,那么B到不了C,A到不了B和C,C到不了B。但如果把他看作是无向图,那么他们也能满足连通条件。

    2. 强连通分量

    整个图并不是强连通的,但是在某些局部区域,他确实也符合强连通的要求,如下图,整张图不算是强连通,但是局部还是能满足强连通条件的。
    在这里插入图片描述

    二、两种dfs遍历

    1. 方式1

    先访问当前节点,再递归相邻节点
    在这里插入图片描述

    • 如上图所示,先访问A,将A标记为已访问之后,我再去访问B,依次下去,B这个分支访问完了,再退回来dfs(F)。如果发现当前节点已经被访问过了,直接结束。因为既然已经被访问过了,那么他相邻的点必然也被访问过来,自然无需访问。

    2. 方式2

    先递归相邻节点,再访问当前节点
    在这里插入图片描述

    • 如上图所示,实际上就是顺序变了,有点像二叉树的后序遍历?对,就是后序遍历,这也是tarjan算法的核心。

    三、一个简单例子理解算法

    • 对于节点x,我有两个变量来表示他的信息,i表示访问顺序(时间戳),j表示按照方向进行访问,能够访问到的最早的节点的时间戳
      在这里插入图片描述

    • 如上,A的时间戳为1,B时间戳为2,C时间戳为3,D时间戳为4

    • A能访问到的最早的时间戳为1,B能访问到的最早的时间戳为2,C能先访问D,再访问到B所以最早时间戳也为2,D也是,能访问到的最早时间戳为2

    • 有相同j值的节点构成一个强连通区域,如上图,B、C、D构成一个强连通区域,A自己构成一个强连通区域

    四、更完整的一个例子

    在这里插入图片描述

    • 这里肯定会有人问,那我通过什么方法来更新j的值呢,这里我们可以根据打印顺序来进行寻找,先打印EE只能访问到自己,于是E(5,5),然后打印DD可以访问到B,于是D(4,2),然后打印CC能访问到DD有最早时间戳2,于是C(2,2),然后再打印BB(2,2),然后开始DFS(F),说明之前的确实已经完成了打包了,B、C、D是一个强连通域,接着如上面步骤,找出AFG这个强连通域

    五、Code实现

    public class Main {
        static int time = 1;
        static Stack<Integer> stack = new Stack<>();
        static int[] dfn;//表示i属性
        static int[] low;//表示j属性
        static int n;//节点个数
    
        public static void main(String[] args) {
            n = 10;
            dfn = new int[n];//初始化
            low = new int[n];//初始化
            for (int i = 0; i < n; i++) {
                if (dfn[i] == 0) {
                    DFS(i);
                }
            }
        }
    
        public static void DFS(int x) {
            stack.push(x);
            dfn[x] = time;
            low[x] = time;
            time++;
            for (int y = 0; y < n; y++) {
                if (x和y是连通的) {
                    if (dfn[y] == 0) {//y这个节点没有被访问过
                        DFS(y);
                        low[x] = Math.min(low[x], low[y]);//更新最早时间戳
                    } else if (如果y已经被访问过了,但是y在stack里面){
                        low[x] = Math.min(low[x], low[y]);
                    }
                }
            }
            if (dfn[x] == low[x]) {//如果我将他整个儿子都完成了遍历,结果他的访问时间戳和最早时间戳相等,说明我整个强连通分量的节点全部访问完了
                stack.pop();
            }
        }
    }
    
    展开全文
  • Tarjan算法详细讲解

    千次阅读 2020-07-06 13:54:48
    Tarjan算法讲解的博客网上找到三篇比较好的,现在都转载了,个人只研究了第一篇,正如博主所说,讲的标比较详细,清晰,剩下两篇也可以看一下. 卿学姐视频讲解https://www.bilibili.com/video/av7330663/ 以下内容转自:...

     

    Tarjan算法讲解的博客网上找到三篇比较好的,现在都转载了,个人只研究了第一篇,正如博主所说,讲的标比较详细,清晰,剩下两篇也可以看一下.

    卿学姐视频讲解 https://www.bilibili.com/video/av7330663/

    以下内容转自:http://www.cnblogs.com/uncle-lu/p/5876729.html

    全网最详细tarjan算法讲解,我不敢说别的。反正其他tarjan算法讲解,我看了半天才看懂。我写的这个,读完一遍,发现原来tarjan这么简单!

    tarjan算法,一个关于 图的联通性的神奇算法。基于DFS(迪法师)算法,深度优先搜索一张有向图。!注意!是有向图。根据树,堆栈,打标记等种种神(che)奇(dan)方法来完成剖析一个图的工作。而图的联通性,就是任督二脉通不通。。的问题。
    了解tarjan算法之前你需要知道:
    强连通,强连通图,强连通分量,解答树(解答树只是一种形式。了解即可)
    不知道怎么办!!!
    在这里插入图片描述
    神奇海螺~:嘟噜噜~!
    强连通(strongly connected): 在一个有向图G里,设两个点 a b 发现,由a有一条路可以走到b,由b又有一条路可以走到a,我们就叫这两个顶点(a,b)强连通。

    强连通图: 如果 在一个有向图G中,每两个点都强连通,我们就叫这个图,强连通图。

    强连通分量strongly connected components):在一个有向图G中,有一个子图,这个子图每2个点都满足强连通,我们就叫这个子图叫做 强连通分量 [分量::把一个向量分解成几个方向的向量的和,那些方向上的向量就叫做该向量(未分解前的向量)的分量]
    举个简单的栗子:
    在这里插入图片描述
    比如说这个图,在这个图中呢,点1与点2互相都有路径到达对方,所以它们强连通.

    而在这个有向图中,点1 2 3组成的这个子图,是整个有向图中的强连通分量。

    解答树:就是一个可以来表达出递归枚举的方式的树(图),其实也可以说是递归图。。反正都是一个作用,一个展示从“什么都没有做”开始到“所有结求出来”逐步完成的过程。“过程!”

    神奇海螺结束!!!
    在这里插入图片描述
    tarjan算法,之所以用DFS就是因为它将每一个强连通分量作为搜索树上的一个子树。而这个图,就是一个完整的搜索树。
    为了使这颗搜索树在遇到强连通分量的节点的时候能顺利进行。每个点都有两个参数。
    1.DFN[]作为这个点搜索的次序编号(时间戳),简单来说就是 第几个被搜索到的。%每个点的时间戳都不一样%。
    2.LOW[]作为每个点在这颗树中的,最小的子树的根,每次保证最小,like它的父亲结点的时间戳这种感觉。如果它自己的LOW[]最小,那这个点就应该从新分配,变成这个强连通分量子树的根节点。
    ps:每次找到一个新点,这个点LOW[]=DFN[]。

    而为了存储整个强连通分量,这里挑选的容器是,堆栈。每次一个新节点出现,就进站,如果这个点有 出度 就继续往下找。直到找到底,每次返回上来都看一看子节点与这个节点的LOW值,谁小就取谁,保证最小的子树根。如果找到DFN[]==LOW[]就说明这个节点是这个强连通分量的根节点(毕竟这个LOW[]值是这个强连通分量里最小的。)最后找到强连通分量的节点后,就将这个栈里,比此节点后进来的节点全部出栈,它们就组成一个全新的强连通分量。

    先来一段伪代码压压惊:

    tarjan(u){
      DFN[u]=Low[u]=++Index // 为节点u设定次序编号和Low初值
      Stack.push(u)   // 将节点u压入栈中
      for each (u, v) in E // 枚举每一条边
        if (v is not visted) // 如果节点v未被访问过
            tarjan(v) // 继续向下找
            Low[u] = min(Low[u], Low[v])
        else if (v in S) // 如果节点u还在栈内
            Low[u] = min(Low[u], DFN[v])
      if (DFN[u] == Low[u]) // 如果节点u是强连通分量的根
      repeat v = S.pop  // 将v退栈,为该强连通分量中一个顶点
      print v
      until (u== v)
    }
    

    首先来一张有向图。网上到处都是这个图。我们就一点一点来模拟整个算法。
    在这里插入图片描述
    从1进入 DFN[1]=LOW[1]= ++index ----1
    入栈 1
    由1进入2 DFN[2]=LOW[2]= ++index ----2
    入栈 1 2
    之后由2进入3 DFN[3]=LOW[3]= ++index ----3
    入栈 1 2 3
    之后由3进入 6 DFN[6]=LOW[6]=++index ----4
    入栈 1 2 3 6
    在这里插入图片描述
    之后发现 嗯? 6无出度,之后判断 DFN[6]==LOW[6]
    说明6是个强连通分量的根节点:6及6以后的点 出栈。
    栈: 1 2 3
    之后退回 节点3 Low[3] = min(Low[3], Low[6]) LOW[3]还是 3
    节点3 也没有再能延伸的边了,判断 DFN[3]==LOW[3]
    说明3是个强连通分量的根节点:3及3以后的点 出栈。
    栈: 1 2
    之后退回 节点2 嗯?!往下到节点5
    DFN[5]=LOW[5]= ++index -----5
    入栈 1 2 5
    在这里插入图片描述
    ps:你会发现在有向图旁边的那个丑的(划掉)搜索树 用红线剪掉的子树,那个就是强连通分量子树。每次找到一个。直接。一剪子下去。半个子树就没有了。。

    结点5 往下找,发现节点6 DFN[6]有值,被访问过。就不管它。
    继续 5往下找,找到了节点1 他爸爸的爸爸。。DFN[1]被访问过并且还在栈中,说明1还在这个强连通分量中,值得发现。 Low[5] = min(Low[5], DFN[1])
    确定关系,在这棵强连通分量树中,5节点要比1节点出现的晚。所以5是1的子节点。so
    LOW[5]= 1

    由5继续回到2 Low[2] = min(Low[2], Low[5])
    LOW[2]=1;
    由2继续回到1 判断 Low[1] = min(Low[1], Low[2])
    LOW[1]还是 1
    1还有边没有走过。发现节点4,访问节点4
    DFN[4]=LOW[4]=++index ----6
    入栈 1 2 5 4
    由节点4,走到5,发现5被访问过了,5还在栈里,
    Low[4] = min(Low[4], DFN[5]) LOW[4]=5
    说明4是5的一个子节点。
    在这里插入图片描述
    由4回到1.

    回到1,判断 Low[1] = min(Low[1], Low[4])
    LOW[1]还是 1 。

    判断 LOW[1] == DFN[1]
    诶?!相等了 说明以1为根节点的强连通分量已经找完了。
    将栈中1以及1之后进栈的所有点,都出栈。
    栈 :(鬼都没有了)

    这个时候就完了吗?!

    你以为就完了吗?!

    然而并没有完,万一你只走了一遍tarjan整个图没有找完怎么办呢?!

    所以。tarjan的调用最好在循环里解决。

    like 如果这个点没有被访问过,那么就从这个点开始tarjan一遍。

    因为这样好让每个点都被访问到。

    在这里插入图片描述
    来一道裸代码。
    输入:
    一个图有向图。
    输出:
    它每个强连通分量。

    这个图就是刚才讲的那个图。一模一样。

    input:
    6 8
    1 3
    1 2
    2 4
    3 4
    3 5
    4 6
    4 1
    5 6
     
    output:
    6
    5
    3 4 2 1
    
    #include<cstdio>
    #include<algorithm>
    #include<string.h>
    using namespace std;
    struct node {
        int v,next;
    }edge[1001];
    int DFN[1001],LOW[1001];
    int stack[1001],heads[1001],visit[1001],cnt,tot,index;
    void add(int x,int y)
    {
        edge[++cnt].next=heads[x];
        edge[cnt].v = y;
        heads[x]=cnt;
        return ;
    }
    void tarjan(int x)//代表第几个点在处理。递归的是点。
    {
        DFN[x]=LOW[x]=++tot;// 新进点的初始化。
        stack[++index]=x;//进站
        visit[x]=1;//表示在栈里
        for(int i=heads[x];i!=-1;i=edge[i].next)
        {
            if(!DFN[edge[i].v]) {//如果没访问过
                tarjan(edge[i].v);//往下进行延伸,开始递归
                LOW[x]=min(LOW[x],LOW[edge[i].v]);//递归出来,比较谁是谁的儿子/父亲,就是树的对应关系,涉及到强连通分量子树最小根的事情。
            }
            else if(visit[edge[i].v ]){  //如果访问过,并且还在栈里。
                LOW[x]=min(LOW[x],DFN[edge[i].v]);//比较谁是谁的儿子/父亲。就是链接对应关系
            }
        }
        if(LOW[x]==DFN[x]) //发现是整个强连通分量子树里的最小根。
        {
            do{
                printf("%d ",stack[index]);
                visit[stack[index]]=0;
                index--;
            }while(x!=stack[index+1]);//出栈,并且输出。
            printf("\n");
        }
        return ;
    }
    int main()
    {
        memset(heads,-1,sizeof(heads));
        int n,m;
        scanf("%d%d",&n,&m);
        int x,y;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&x,&y);
            add(x,y);
        }
        for(int i=1;i<=n;i++)
             if(!DFN[i])  tarjan(1);//当这个点没有访问过,就从此点开始。防止图没走完
        return 0;
    }
    

    以下内容转自:http://blog.csdn.net/jeryjeryjery/article/details/52829142

    在有向图G中,如果两个顶点间至少存在一条路径,称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通,称G是一个强连通图。非强连通图有向图的极大强连通子图,称为强连通分量(strongly connected components)。
    如下图中,强连通分量有:{1,2,3,4},{5},{6}
    在这里插入图片描述
    Tarjan算法是基于对图深度优先搜索的算法,每个强连通分量为搜索树中的一棵子树。搜索时,把当前搜索树中未处理的节点加入一个堆栈,回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。Tarjan算法有点类似于基于后序的深度遍历搜索和并查集的组合,充分利用回溯来解决问题。
    在Tarjan算法中为每个节点i维护了以下几个变量:
    DFN[i]:深度优先搜索遍历时节点i被搜索的次序。
    low[i]:节点i能够回溯到的最早位于栈中的节点。
    flag[i]:标记几点i是否在栈中。

    Tarjan算法的运行过程:
    1.首先就是按照深度优先搜索算法搜索的次序对图中所有的节点进行搜索。
    2.在搜索过程中,对于任意节点u和与其相连的节点v,根据节点v是否在栈中来进行不同的操作:
    *节点v不在栈中,即节点v还没有被访问过,则继续对v进行深度搜索。
    *节点v已经在栈中,即已经被访问过,则判断节点v的DFN值和节点u的low值的大小来更新节点u的low值。如果节点v的 DFN值要小于节点u的low值,根据low值的定义(能够回溯到的最早的已经在栈中的节点),我们需要用DFN值来更新u 的low值。
    3.在回溯过程中,对于任意节点u与其子节点v(其实不能算是子节点,只是在深度遍历的过程中,v是在u之后紧挨着u的节点)的 low值来更新节点u的low值。因为节点v能够回溯到的已经在栈中的节点,节点u也一定能够回溯到。因为存在从u到v的直接路 径,所以v能够到的节点u也一定能够到。
    4.对于一个连通图,我们很容易想到,在该连通图中有且仅有一个节点u的DFN值和low值相等。该节点一定是在深度遍历的过 程中,该连通图中第一个被访问过的节点,因为它的DFN值和low值最小,不会被该连通图中的其他节点所影响。下面我们证 明为什么仅有一个节点的DFN和low值相等。假设有两个节点的DFN值和low值相等,由于这两个节点的DFN值一定不相同 (DFN值的定义就是深度遍历时被访问的先后
    次序),所以两个的low值也绝对不相等。由于位于同一个连通图中,所以两个节点必定相互可达,那么两者的low值一定会 被另外一个所影响(要看谁的low值更小),所以不可能存在两对DFN值和low值相等的节点。

    所以我们在回溯的过程中就能够通过判断节点的low值和DFN值是否相等来判断是否已经找到一个子连通图。由于该连通图中 的DFN值和low值相等的节点是该连通图中第一个被访问到的节点,又根据栈的特性,则该节点在最里面。所以能够通过不停 的弹栈,直到弹出该DFN值和low值相同的节点来弹出该连通图中所有的节点。

    Tarjan算法的C++实现代码如下,可以配合上面的图加以理解:

    #include<iostream>
    using namespace std;
    int DFN[105];                                  //记录在做dfs时节点的搜索次序
    int low[105];                                  //记录节点能够找到的最先访问的祖先的记号
    int count=1;                                   //标记访问次序,时间戳
    int stack[105];                                //压入栈中
    int top=-1;
    int flag[105];                                 //标记节点是否已经在栈中
    int number=0;
    int j;
    int matrix[105][105]={{0,1,1,0,0,0},{0,0,0,1,0,0},{0,0,0,1,1,0},{1,0,0,0,0,1},{0,0,0,0,0,1},{0,0,0,0,0,0}};
    int length;                                    //图的长度
    void tarjan(int u){
        DFN[u]=low[u]=count++;                     //初始化两个值,自己为能找到的最先访问的祖先
        stack[++top]=u;
        flag[u]=1;                                 //标记为已经在栈中
     
        for(int v=0;v<length;v++){
    	if(matrix[u][v]){
    	    if(!DFN[v]){                       //如果点i没有被访问过
    		tarjan(v);                     //递归访问
    		if(low[v]<low[u])
    		    low[u]=low[v];             //更新能找的到祖先
    	    }
    	    else{                              //如果访问过了,并且该点的DFN更小,则
    		if(DFN[v]<low[u]&&flag[v])     //flag[v]这个判断条件很重要,这样可以避免已经确定在其他联通图的v,因为u到v的单向边而影响到u的low
    		low[u]=DFN[v];                 //也就是已经确定了的联通图要剔除掉,剔除的办法就是判断其还在栈中,因为已经确定了的连通图的点
    	    }                                  //flag在下面的do while中已经设为0了(即已经从栈中剔除了)
    	}
        }
     
        //往后回溯的时候,如果发现DFN和low相同的节点,就可以把这个节点之后的节点全部弹栈,构成连通图
        if(DFN[u]==low[u]){
    	number++;                               //记录连通图的数量
    	do{
    	    j=stack[top--];                     //依次取出,直到u
    	    cout<<j<<" ";
    	    flag[j]=0;                          //设置为不在栈中
    	}while(j!=u);
    	    cout<<endl;
        }
    }
    int main(){
    	
        memset(DFN,0,sizeof(DFN));                  //数据的初始化
        memset(low,0,sizeof(low));
        memset(flag,0,sizeof(flag));
    	
        length=6;
        tarjan(0);
     
        cout<<endl;
        for(int i=0;i<6;i++){
    	cout<<"DFN["<<i<<"]:"<<DFN[i]<<" low["<<i<<"]:"<<low[i]<<endl;
        }
        return 0;
    }
    

    以下内用转自:http://blog.csdn.net/wsniyufang/article/details/6604458

    [有向图强连通分量]
    在有向图G中,如果两个顶点间至少存在一条路径,称两个顶点强连通(stronglyconnected)。如果有向图G的每两个顶点都强连通,称G是一个强连通图。非强连通图有向图的极大强连通子图,称为强连通分量(strongly connected components)。

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

    在这里插入图片描述

    直接根据定义,用双向遍历取交集的方法求强连通分量,时间复杂度为O(N^2+M)。更好的方法是Kosaraju算法或Tarjan算法,两者的时间复杂度都是O(N+M)。本文介绍的是Tarjan算法。

    [Tarjan算法]

    Tarjan算法是基于对图深度优先搜索的算法,每个强连通分量为搜索树中的一棵子树。搜索时,把当前搜索树中未处理的节点加入一个堆栈,回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。

    定义DFN(u)为节点u搜索的次序编号(时间戳),Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号。由定义可以得出,

    当DFN(u)=Low(u)时,以u为根的搜索子树上所有节点是一个强连通分量。

    算法伪代码如下:

    tarjan(u)
    {
        DFN[u]=Low[u]=++Index        // 为节点u设定次序编号和Low初值
        Stack.push(u)                // 将节点u压入栈中
        for each (u, v) in E         // 枚举每一条边
            if (v is not visted)        // 如果节点v未被访问过
                tarjan(v)                  // 继续向下找
                Low[u] = min(Low[u], Low[v])
            else if (v in S)            // 如果节点u还在栈内
                Low[u] = min(Low[u], DFN[v])
        if (DFN[u] == Low[u])        // 如果节点u是强连通分量的根
            repeat
                v = S.pop                 // 将v退栈,为该强连通分量中一个顶点
                print v
            until (u== v)
    }
    

    接下来是对算法流程的演示。

    从节点1开始DFS,把遍历到的节点加入栈中。搜索到节点u=6时,DFN[6]=LOW[6],找到了一个强连通分量。退栈到u=v为止,{6}为一个强连通分量。

    在这里插入图片描述

    返回节点5,发现DFN[5]=LOW[5],退栈后{5}为一个强连通分量。

    在这里插入图片描述

    返回节点3,继续搜索到节点4,把4加入堆栈。发现节点4像节点1的后向边,节点1还在栈中,所以LOW[4]=1。节点6已经出栈,不再访问6,返回3,(3,4)为树枝边,所以LOW[3]=LOW[4]=1。

    在这里插入图片描述

    继续回到节点1,最后访问节点2。访问边(2,4),4还在栈中,所以LOW[2]=4。返回1后,发现DFN[1]=LOW[1],把栈中节点全部取出,组成一个连通分量{1,3,4,2}。

    在这里插入图片描述
    至此,算法结束。经过该算法,求出了图中全部的三个强连通分量{1,3,4,2},{5},{6}。

    可以发现,运行Tarjan算法的过程中,每个顶点都被访问了一次,且只进出了一次堆栈,每条边也只被访问了一次,所以该算法的时间复杂度为O(N+M)。

    求有向图的强连通分量还有一个强有力的算法,为Kosaraju算法。Kosaraju是基于对有向图及其逆图两次DFS的方法,其时间复杂度也是 O(N+M)。与Trajan算法相比,Kosaraju算法可能会稍微更直观一些。但是Tarjan只用对原图进行一次DFS,不用建立逆图,更简洁。 在实际的测试中,Tarjan算法的运行效率也比Kosaraju算法高30%左右。此外,该Tarjan算法与求无向图的双连通分量(割点、桥)的Tarjan算法也有着很深的联系。学习该Tarjan算法,也有助于深入理解求双连通分量的Tarjan算法,两者可以类比、组合理解。

    求有向图的强连通分量的Tarjan算法是以其发明者Robert Tarjan命名的。Robert Tarjan还发明了求双连通分量的Tarjan算法,以及求最近公共祖先的离线Tarjan算法,在此对Tarjan表示崇高的敬意。

    代码:

    void tarjan(int i)
    {
        int j;
        DFN[i]=LOW[i]=++Dindex;
        instack[i]=true;
        Stap[++Stop]=i;
        for (edge *e=V[i]; e; e=e->next)
        {
            j=e->t;
            if (!DFN[j])
            {
                tarjan(j);
                if (LOW[j]<LOW[i])
                    LOW[i]=LOW[j];
            }
            else if (instack[j] && DFN[j]<LOW[i])
                LOW[i]=DFN[j];
        }
        if (DFN[i]==LOW[i])
        {
            Bcnt++;
            do
            {
                j=Stap[Stop--];
                instack[j]=false;
                Belong[j]=Bcnt;
            }
            while (j!=i);
        }
    }
    void solve()
    {
        int i;
        Stop=Bcnt=Dindex=0;
        memset(DFN,0,sizeof(DFN));
        for (i=1; i<=N; i++)
            if (!DFN[i])
                tarjan(i);
    }

    https://blog.csdn.net/Prediction__/article/details/100030166 

    展开全文
  • Tarjan 算法

    2021-04-24 11:25:49
    Tarjan 算法 一.算法简介 Tarjan 算法一种由Robert Tarjan提出的求解有向图强连通分量的算法,它能做到线性时间的复杂度。 我们定义: 如果两个顶点可以相互通达,则称两个顶点强连通(strongly connected)。...
  • 浅谈Tarjan算法

    2022-02-17 23:18:01
    Tarjan算法Tarjan算法是一种用于查找已知图中的强连通分量的方法(介绍似乎越来越草率了 时间复杂度:O(n+m)//n为点数,m为边数 算法思路: 1,首先对每个节点设置两个参数存储:dfn[i]表示第i个点被搜索...
  • tarjan算法

    2011-10-14 16:31:02
    Tarjan算法是用来求有向图的强连通分量的。求有向图的强连通分量的Tarjan算法是以其发明者Robert Tarjan命名的。Robert Tarjan还发明了求双连通分量的Tarjan算法,以及求最近公共祖先的离线Tarjan算法 (本篇文章...
  • 全网最详细解释tarjan算法

    千次阅读 2021-08-20 21:24:23
    tarjan算法 tarjan算法是为了计算强连通分量的 强连通分量也就是在有向图当中,能够双方都能够到达对方的点集 视频链接 代码实现 #include <bits/stdc++.h> using namespace std; int times = 1; // 时间搓 ...
  • Tarjan算法例题及模板

    2022-02-05 16:42:18
    } void tarjan(int u) { dfn[u] = low[u] = ++ timestamp; stk[ ++ top] = u, in_stk[u] = true; for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if (!dfn[j]) { tarjan(j); low[u] = min(low[u], low[j]); } ...
  • 有向图的极大连通子图被称为强连通分量 7、Tarjan算法是基于深度优先搜索的算法,用于求解图的连通性问题。Tarjan算法可以在线性时间内求出无向图的割点与桥,进一步地可以求解无向图的双连通分量;同时,也可以求解...
  • Tarjan是使用Tarjan算法的图循环检测功能。 该算法获取输入图并生成一个切片,其中每个项目都是一个高度连接的顶点的切片。 输入图采用地图的形式,其中键是图形顶点,值是一个切片的for的边。 算法说明: : ...
  • Tarjar算法可以解决很多连通性问题,我的上一篇文章是用Tarjan解决强联通分量问题。 我们用dfn[ ]数组记录一个节点的遍历编号,也就是第几次遍历到的点。low[ ]代表一个节点能到达最小的点,不经过父节点。 比如 1....
  • 在看Tarjan算法之前先看以下概念: 给定无向图连通图G=(V,E)。 若对于 x∈V ,从图中删除节点x以及与x关联的所有边之后,G 分裂为两个或者以上的连通块,则称节点 x 为无向连通图 G 的割点。 若对于 e∈E ,删除边 e...
  • Tarjan算法超详细讲解(割点割边强连通)

    千次阅读 多人点赞 2020-02-06 15:27:37
    今天我主要介绍Tarjan算法在割点割边以及强连通分量中的应用以及缩点技巧 按照老规矩, 先上两道模板题 【模板】强连通分量 【模板】割点(割顶) 割点割边 一, 离散数学中的定义: 割点: 无向连通图中,去掉一个顶点...
  • 一、Tarjan算法简介 Tarjan算法是由Robert Tarjan发明的一种基于DFS的图论算法,他可以用来求解有向图的强联通 分量或者求解无向图的中的割点和桥等,可以说是图论算法中的基本算法之一。本文将以求解有向 图的强...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,903
精华内容 5,961
关键字:

tarjan算法