Menu
Article ACM

算法学习——求割点与桥的tarjan算法 HDU4738

NodeKey

NodeKey

• 4 min read

前天打周赛做到 HDU4738 绞尽脑汁都没想到用什么好的方法来解决这个问题 周赛结束之后跟Yasola和xcy讨论了一下居然用到 tarjan算法 exm？？？ tarjan不是用来求 lca的么？？？

回去怒补了一发才知道 tarjan原来是一系列是算法 根据我看到的博客原文 可以这么说 tarjan是个天才 他伟大的一生创造了无数的算法 统称 tarjan算法 其中有三个最有名的 求lca 求图的割点与桥 （还有一个啥来着 反正我最近一定要学一下 无奈看完之后就断电熄灯了 一直拖到昨晚才学

基本概念：

图论里的桥 即 连接两个子图唯一边 如果这条边被你砍了 整个图将被你一分为二

图论里的割点 同桥的理解 只是对象是一个结点 如果这个结点被你分开 那么整个图也将分裂

因为我也是刚学 hdu4738 的对象也是一张无向图 以下均以无向图进行讨论 有向图日后再说

在tarjan算法中 对于一张图 我以深搜为核心 并且每个节点只访问一次 那么最后深搜得到的图 会是什么？？

是一棵树！！ （这真是太奇妙了 我自认为对搜索有点信心 但是从来没有想过这样的应用

于是有如下定理：

在无向连通图G中

1.根结点为割点 当且仅当它有两个及以上的子结点

2.非根节点为割点 当且仅当 u 存在结点 v 及其所有后代都没有反向边可以返回 u 的祖先 （不包括 u

我们在深搜过程中每一个节点都有他的访问次序 我们定义一个 时间戳 dfn 来表示

另外我们还需要一个 定义一个 low 表示 该结点反向能达到的最小的 dfn （ 初始都是 low=dfn

虽然我们深搜出一棵树 但是我们的研究对象还是原图 对于原图来说 每一个结点都会有若干条边

如果在这时 我的结点 u 有一条到 v 的边 而且 low[v] <= dfn[u] 这就表示在 u 结点有一条边 可以返回到之前的结点 并形成一个环 那么显而易见 这根本不会是桥

相反 只要对每一个边访问 若 low[v] > dfn [u] 那么这条边即为 桥

大犇都是先理解割点再理解桥的 像我这种菜鸡只能从 割点的特殊情况桥 开始理解

对于割点的话道理 还是差不多 无非是一个 等号的问题

在判断桥中 如果 low[v]==dfn[u] 那么这意味着始末都是这个 u 结点的一个 环而已 （包括自环） 没什么影响 只要是环 那么必然不是桥

而对于割点 如果 low[v]==dfn[u] 那么v及其所有子结点都必须通过 u 结点来访问 u 的祖先 所以 u 仍然是割点

附带 HDU 4738 Caocao’s Bridges

这题就是很裸的求桥的问题 只不过 求最短的桥 并且有两个坑点

我们在用tarjan 的时候吧每个桥都保存在一个数组中 最后for 一遍即可

而坑点包括

1.原图可能不联通 这时不需要派人去炸桥 直接输出 0

2.有重边

3.可能有权值为0的桥 但我们必须要有一个人去带炸弹啊 所以这是输出 1

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1010;
int n, m, indx, vis_time, union_num, ansn;
int head[maxn], low[maxn], dfn[maxn], ans[maxn];

struct node {
    int to;
    int next;
    int w;
};
node edge[2 * maxn * maxn];

void AddEdge(int u, int v, int w)
{
    edge[indx].to = v;
    edge[indx].w = w;
    edge[indx].next = head[u];
    head[u] = indx++;

    edge[indx].to = u;
    edge[indx].w = w;
    edge[indx].next = head[v];
    head[v] = indx++;
}

void init()
{
    vis_time = indx = ansn = 0;
    union_num = 1;
    memset(head, -1, sizeof head);
    memset(dfn, 0, sizeof dfn);
    memset(low, 0, sizeof low);
}

void tarjan(int u, int father)
{
    low[u] = dfn[u] = ++vis_time;
    int pre_num = 0;
    for (int id = head[u]; id != -1; id = edge[id].next) {
        int v = edge[id].to;
        if (v == father && pre_num == 0) {
            pre_num++;
            continue;
        }
        if (!dfn[v]) {
            union_num++;
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u])
                ans[ansn++] = edge[id].w;
        } else if (dfn[v] < dfn[u])
            low[u] = min(low[u], dfn[v]);
    }
}

int main()
{
    int u, v, w;
    while (scanf("%d %d", &n, &m) != EOF) {
        if (n == 0 && m == 0)
            break;
        init();
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &u, &v, &w);
            AddEdge(u, v, w);
        }
        tarjan(1, 1);
        if (union_num < n)
            puts("0");
        else {
            int true_ans = inf;
            for (int i = 0; i < ansn; i++)
                if (true_ans > ans[i])
                    true_ans = ans[i];
            if (true_ans == 0)
                true_ans++;
            else if (true_ans == inf)
                true_ans = -1;
            printf("%d\n", true_ans);
        }
    }
    return 0;
}
Share