Tarjan 算法(超详细!!)

这篇具有很好参考价值的文章主要介绍了Tarjan 算法(超详细!!)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

推荐在 cnblogs 上阅读

Tarjan 算法

前言

说来惭愧,这个模板仅是绿的算法至今我才学会。

我还记得去年 CSP2023 坐大巴路上拿着书背 Tarjan 的模板。虽然那年没有考连通分量类似的题目。

现在做题遇到了 Tarjan,那么,重学,开写!

另,要想学好此算法的第一件事——膜拜 Tarjan 爷爷。

Tarjan 算法(超详细!!),算法篇,算法,深度优先,图论,c++,笔记

Tarjan 算法到底是什么

其实广义上有许多算法都是 Tarjan 发明的(大名鼎鼎的 Link-Cut-Tree 正是出自他手),而本文介绍的是可以解决图中强连通分量的算法。

也就是狭义的 Tarjan 算法。

什么是强连通分量

对于一个图 G G G 来说,一个字图中,任意两点都可以彼此到达(存在路径),这个子图就称为图 G G G 的强连通分量。特别地,一个点也是一个强连通分量。

算法思路

Tarjan 是基于 DFS 实现的,走过的边会形成一棵搜索树。可以看作是原图删去一些边留下来而形成的。

看个图吧:

Tarjan 算法(超详细!!),算法篇,算法,深度优先,图论,c++,笔记

如果我们把抛弃的边分为三个大类,可以分为:

  1. 横叉边(红)
  2. 前向边(黄)
  3. 后向边(蓝)

上图把抛弃的边画出来就是这样了:

Tarjan 算法(超详细!!),算法篇,算法,深度优先,图论,c++,笔记

容易发现,能够构成环的只有前向边。而我们所需要得到的连通分量,正需要环。

我们怎么知道 DFS 到什么时候是一条前向边呢?

我们可以在 DFS 过程中给每个点打一个时间戳(实际上就是 DFS 序, dfn[x]=++cnt),如此,当我们遍历某节点的儿子 v v v 时, v v v 是一个已访问过的节点,那么我们找到了后向边。

如何维护?——用两个数组

  1. dfn[i]:储存时间戳。
  2. low[i]:储存 i i i 点可以访问到的最高祖先的 dfn 值(因为 DFS 序由小到大,所以储存的数越小、表示 i i i 点访问祖先能力越强)。

特殊地,一个点访问祖先的能力再差,也可以访问到自己。

代码实现

code文章来源地址https://www.toymoban.com/news/detail-822658.html

int dfn[MAXN],low[MAXN],tim;
bool vis[MAXN];
int ans;
stack<int> st;
int belong[MAXN];
vector<int> G[MAXN];
void tarjan(int x)
{
    dfn[x]=low[x]=++tim;
    st.push(x);
    vis[x]=1;
    for(int i=hd[x];i;i=lt[i])
    {
        int v=en[i];
        if(!dfn[v])
        {
            tarjan(v);
            low[x]=min(low[x],low[v]);
        }
        else if(vis[v]) // 此时找到后向边,不着急操作,等待回溯以后在操作
            low[x]=min(low[x],dfn[v]);
    }
    if(dfn[x]==low[x]) // 这是根节点独有的性质
    {
        ++ans; // 看看目前已经是第几个强连通分量了
        int top;
        do
        {
            top=st.top();st.pop();
            vis[top]=0;
            belong[top]=ans; // belong[] : 某节点属于那个强连通分量
            G[ans].push_back(top); // 强连通分量有哪些成员节点。
        } while (top!=x);
    }
}

P1726 上白泽慧音

题目要求:求出最大强连通分量、并输出其成员。如数量相同,输出最小的成员集合。

此题目中,belong[] 就不需要了,存成员是必要的;按字典序输出的话,把成员丢进优先队列带走,秒了!

code

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

#define int long long

const int MAXN=2e5+5;

int n,m;
int dfn[MAXN],low[MAXN],tim;
bool vis[MAXN];
int ans;
stack<int> st;
int belong[MAXN];
int su,hd[MAXN],lt[MAXN],en[MAXN];
priority_queue<int,vector<int>,greater<int>> G[MAXN];
struct node
{
    int id,sz,val;
}p[MAXN];

void add(int u,int v)
{
    en[++su]=v,lt[su]=hd[u],hd[u]=su;
}

void tarjan(int x)
{
    dfn[x]=low[x]=++tim;
    st.push(x);
    vis[x]=1;
    for(int i=hd[x];i;i=lt[i])
    {
        int v=en[i];
        if(!dfn[v])
        {
            tarjan(v);
            low[x]=min(low[x],low[v]);
        }
        else if(vis[v])
            low[x]=min(low[x],dfn[v]);
    }
    if(dfn[x]==low[x])
    {
        ++ans;
        p[ans].id=ans;
        p[ans].val=st.top();
        int top;
        do
        {
            top=st.top();st.pop();
            vis[top]=0;
            belong[top]=ans;
            p[ans].sz++;
            G[ans].push(top);
        } while (top!=x);
    }
}

signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1,u,v,w;i<=m;i++)
    {
        scanf("%lld%lld%lld",&u,&v,&w);
        add(u,v);
        if(w==2) add(v,u);
    }
  
    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);

    sort(p+1,p+ans+1,[](node x,node y){
        return x.sz==y.sz?x.val<y.val:x.sz>y.sz;
    });

    printf("%lld\n",p[1].sz);
    while (!G[p[1].id].empty())
    {
        printf("%lld ",G[p[1].id].top());
        G[p[1].id].pop();
    }
  
    return 0;
}

参考文献

  • [1] _H1kar1,题解 P1726 【上白泽慧音】

到了这里,关于Tarjan 算法(超详细!!)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包