首页 > 编程语言 >Tarjan算法详解

Tarjan算法详解

时间：2023-03-14 13:23:32浏览次数：49  
标签：Tarjan 10001 int 连通 long 算法 详解 节点 分量

Tarjan算法介绍

TarjanTarjan算法是用于在有向图中求强连通分量的算法

这里给出强连通分量的定义：

有向图中一个最大的图，使这个图中每个两点都能够互相到达。这个最大的图称为强连通分量，同时一个点也属于强连通分量。

据一个简单的例子，下图中的123123也就是一个强连通分量,44也是一个强连通分量：

TarjanTarjan算法基于DFSDFS，对于每一个点遍历一次，可以在O(n)O(n)的时间复杂度求出强连通分量

TarjanTarjan算法的实现

首先介绍两个数组dfndfn和lowlow

他们分别表示该节点遍历到的时间和其可以遍历到的最早的祖先节点

我们发现如果一个从uu遍历到的节点vv的lowlow比uu的dfndfn更小，说明vv肯定连接到了uu的祖先节点，由此形成了一个环也就是一个强连通分量

所以我们很容易想到在遍历的过程中用子节点的lowlow更新该节点的lowlow，接着对于同一个lowlow值的点集，应该就是一个强连通分量了（类似于并查集）

但是实际上我们可以举出两种反例：

反例1

在该反例中，只有一个强连通分量，可是按上述思路却得到了两个，原因是因为节点55使用22的lowlow更新时22的lowlow还没有更新完成

反例2

在该反例中，有两个强连通分量，可是按上述思路确只得到了一个，原因是因为，节点55使用了11的lowlow进行更，可是两者并不属于同一个强连通分量

如何解决这两个问题呢？我们使用栈进行记录即可，这里不再证明使用栈的正确性（因为我不会），想了解的可以简单看看这张图   

简单说说使用栈的作用，就是两个(对应上述反例)：

1.遍历完成后更新整个强连通分量的lowlow

2.遍历完成该强连通分量后，避免使用该强连通分量的lowlow更新其他节点

有了上述解释之后，算法的过程就很好理解了

首先遍历更新

然后使用栈更新即可

割点

割点是TarjanTarjan算法在无向图中的一个应用

割点的定义是对于一个双连通分量（也就是连通块），假如去掉了这个点，双连通分量就会分裂

我们考虑从一个点开始使用TarjanTarjan算法进行遍历

不过这里的TarjanTarjan有点不同，首先我们不需要使用栈，因为我们不需要更新一个连通块的lowlow，也并不需要栈来判断链接不联通的情况，因为是无向图

我们很容易发现 （我注意力又涣散了） 只有两种情况是割点

1.对于根节点，当其存在两个及以上的子节点时，他是割点

2.对于非根节点，当其子节点的low\ge dfnlow≥dfn时，他是割点

分别来感性证明一下

首先对于第一种情况，为什么要求是根节点，因为对于根来说，显然，所以的连通块已经遍历完成，那么此时，当他有多个子节点时，意味着，图中有多个以他作为链接的连通块，所以此时，根节点是割点。而对于非根节点，由于图还没有遍历完，所以其不存在如下性质

对于第二种情况，通俗地说，也就是当某节点的子节点链接道了他的祖先，那么他不为割点（因为形成了环），而反之则为割点，为什么要求是非根节点呢？

因为对于根节点可能存在一条链的情况，此时，他不是割点

tips:上述内容所提及的根于子节点，都是基于TarjanTarjan算法的dfsdfs搜索树

接着是代码实现：

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
const int N=2e4+10;
int n,m;
int u,v;
vector<int>edge[N];
int low[N];
int dfn[N];
bool g[N];
int deep;
int num;
void dfs(int x,int fa)
{
    int child=0;
    deep++;
    low[x]=deep;
    dfn[x]=deep;
    for(int i=0;i<edge[x].size();i++)
    {
        int next=edge[x][i];
        if(dfn[next]==0)
        {
            if(x==fa)
            child++;
            dfs(next,x);
            low[x]=min(low[x],low[next]);
            if(x!=fa&&low[next]>=dfn[x])
            {
                g[x]=true;
            }
        }
        else
        {
            low[x]=min(low[x],dfn[next]);
        }
    }
    if(child>=2)
    {
        g[x]=true;
    }
    return;
}
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
    {
        if(dfn[i]==0)
        {
            dfs(i,i);       
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(g[i]==true)
        {
            num++;
        }
    }
    cout<<num<<endl;
    for(int i=1;i<=n;i++)
    {
        if(g[i]==true)
        {
            cout<<i<<" ";
        }
    }
    return 0;
}

缩点

缩点是基于TarjanTarjan实现的一种算法，他的目的是，将有向图中的强连通分量缩成一个点，从而使原图变成一个有向图无环图，来满足拓扑排序等算法的使用需要

因为思想较为简单所以直接放上模板题的代码（缩点+拓扑排序+DPDP）

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
int n,m;
int u[100001],v[100001];
int l;
int a[10001];
int sum[10001];
bool f[10001];
int z[10001];
int low[10001];
int dfn[10001];
bool vis[10001];
vector<int>edge[10001];
int r[10001];
vector<int>e[10001];//top边 
vector<int>ne[10001];//单向边 
int dp[10001];
int ans;
int deep;
queue<int>q;
void dfs(int x)
{
    deep++;
    dfn[x]=deep;
    low[x]=deep;
    z[++l]=x;
    vis[x]=true;
    for(int i=0;i<edge[x].size();i++)
    {
        int next=edge[x][i];
        if(dfn[edge[x][i]]==0)
        {
            dfs(next);
            low[x]=min(low[x],low[next]);
        }
        else
        {
            if(vis[next]==true)
            {
                low[x]=min(low[x],low[next]);
            }
        }
    }
    if(dfn[x]==low[x])
    {
        while(z[l]!=x)
        {
            low[z[l]]=dfn[x];
            vis[z[l]]=false;
            l--;
        }
        vis[z[l]]=false;
        l--;
    }
    return;
}
void top()
{
    for(int i=1;i<=n;i++)
    {
        if(f[i]==true&&r[i]==0)
        {
            q.push(i);
            r[i]=-1;
        }
    } 
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int i=0;i<e[x].size();i++)
        {
            r[e[x][i]]--;
            if(r[e[x][i]]==0)
            {
                q.push(e[x][i]);
                r[e[x][i]]=-1;
            }
        }
        int maxs=0;
        for(int i=0;i<ne[x].size();i++)//拓扑排序的过程中DP
        {
            maxs=max(maxs,dp[ne[x][i]]);
        }
        dp[x]=sum[x]+maxs;
        ans=max(ans,dp[x]);
    }
    return;
}
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=m;i++)
    {
        cin>>u[i]>>v[i];
        edge[u[i]].push_back(v[i]);
    }
    for(int i=1;i<=n;i++)
    {
        if(dfn[i]==0)
        {
            dfs(i);
        }
    }
    for(int i=1;i<=n;i++)//其实low就可以看作是强连通分量的一个祖先（跟并查集一样）
    {
        sum[low[i]]+=a[i];//每个强连通分量的点数
        f[low[i]]=true;//缩成的点
    }
    for(int i=1;i<=m;i++)
    {
        u[i]=low[u[i]];
        v[i]=low[v[i]];
        if(u[i]!=v[i])//自环不能连边
        {
            r[u[i]]++;
            e[v[i]].push_back(u[i]);
            ne[u[i]].push_back(v[i]);
        }
    }
    top();
    cout<<ans;
    return 0;
}

2-sat

2-sat是TarjanTarjan算法延申出的一个问题

其旨在解决形如

x1|x2=1x1∣x2=1x2|x3=0x2∣x3=0x1\&x2=0x1&x2=0

这样的问题是否有解以及构造解

解决的方法非常的简单，就是在含义如x1=1x1=1和x2=0x2=0之间连一条有向边，表示我应该由x1=1x1=1的状态得出x2=0x2=0的状态

tips，这里有一些常见的问题，例如连接x1=1x1=1到x1=0x1=0表示的什么含义，其实就是表示若x1=1x1=1应该变成x1=0x1=0即x1\ne1x1​=1,x1=0x1=0

然后跑TarjanTarjan，当x=1x=1和x=0x=0出现在同一强连通分量时，意味着出现了x=1x=1要变为x=0x=0并且x=0x=0要变为x=1x=1，出现矛盾，无解

反之有解

至于构造，显然在x=0x=0和x=1x=1中，我们应该选择拓扑序更大的，因为显然连接某状态的边更多说明更多状态会推导出该状态，所以会更优

这里附上模板题及代码 P4782 【模板】2-SAT 问题

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
const int N=1e6+10;
const int M=1e6+10;
int n,m;
int a,op1,b,op2;
vector<int>edge[N*2];//0 1 
int deep;
int dfn[N*2];
int low[N*2];
int z[N*2];
int l;
bool vis[N*2];
int color[N*2];
int colnum;
void dfs(int x)
{
    deep++;
    l++;
    z[l]=x;
    low[x]=deep;
    dfn[x]=deep;
    vis[x]=true;
    for(int i=0;i<edge[x].size();i++)
    {
        int next=edge[x][i];
        if(dfn[next]==0)
        {
            dfs(next);
            low[x]=min(low[x],low[next]);
        }
        else
        {
            if(vis[next]==true)
            {
                low[x]=min(low[x],low[next]);
            }
        }
    }
    if(dfn[x]==low[x])
    {
        colnum++;
        while(z[l]!=x)
        {
            low[z[l]]=low[x];
            vis[z[l]]=false;
            color[z[l]]=colnum;
            l--;
        }
        vis[z[l]]=false;
        color[z[l]]=colnum;
        l--;
    }
    return;
}
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>a>>op1>>b>>op2;
        if(op1==0)
        {
            if(op2==0)
            {
                edge[a+n].push_back(b);
                edge[b+n].push_back(a);
            }
            else
            {
                edge[a+n].push_back(b+n);
                edge[b].push_back(a);
            }
        }
        else
        {
            if(op2==0)
            {
                edge[a].push_back(b);
                edge[b+n].push_back(a+n);
            }
            else
            {
                edge[a].push_back(b+n);
                edge[b].push_back(a+n);
            }
        }
    }
    for(int i=1;i<=n*2;i++)
    {
        if(dfn[i]==0)
        {
            dfs(i);
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(low[i]==low[i+n])
        {
            cout<<"IMPOSSIBLE";
            return 0;
        }
    }
    cout<<"POSSIBLE"<<endl;
    for(int i=1;i<=n;i++)
    {
        if(color[i]<color[i+n])
        cout<<0<<" ";
        else
        cout<<1<<" ";
    }
    return 0;
}

这里存在一个细节，强连通分量的编号越小，说明拓扑序越大。

其实这也比较好理解

举一个例子

图中红蓝两个强连通分量，显然蓝的编号更小，拓扑序越大，因为显然如果一个强连通分量对于别的强连通分量有连边，TarjanTarjan算法会先遍历另外一个强连通分量，然后再对改强连通分量进行更新。

所以先更新的那个强连通分量满足以下两个条件

1.出边少 2.入边多

即拓扑序大，更优

前缀后缀优化点集内建边

这个由于我太菜了，并没有搞懂，所以直接背了 （刚刚逝了逝，发现已经忘了）

提供一篇很好的博客和例题

P6378 [PA2010] Riddle

P6378 [PA2010]Riddle 题解

标签：Tarjan,10001,int,连通,long,算法,详解,节点,分量
From： https://www.cnblogs.com/eveningbreath/p/17214616.html

相关文章

  • K8S部署应用详解
    #前言首先以SpringBoot应用为例介绍一下k8s的发布步骤。1.从代码仓库下载代码，比如GitLab；2.接着是进行打包，比如使用Maven；3.编写Dockerfile文件，把步骤2产生的包制作成镜像......
  • dirsearch web网站目录扫描工具详解
    文章目录​​1dirsearch介绍​​​​2安装​​​​3实战演练​​​​3.1仅指定网址-u​​​​3.2指定网站语言-e​​​​3.3指定字典-w​​​​3.4递归目录-r​......
  • 决策树算法
    fromsklearnimporttreefromsklearn.datasetsimportload_irisfromsklearn.model_selectionimporttrain_test_splitimportnumpyasnpif__name__=="__main__":......
  • k近邻算法
    如果一个样本在特征空间中的k个最“相似”(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别相似度：即两个点的距离来衡量距离越近越近相似度......
  • Python的namedtuple使用详解
    namedtuple又名具名元组，因为普通元组的局限性，不能为元组的数据进行命名，所以我们并不知道一个元组所要表达的意义，所以在这里引入了collections.namedtuple这个工厂函数，来构......
  • SM2算法功能简述（一） 数字签名生成流程
    SM2数字签名算法由一个签名者对数据产生数字签名，并由一个验证者验证签名的可靠性。每个签名者有一个公钥和一个私钥，其中私钥用于产生签名，验证者用签名者的公钥验证签名。在......
  • TCP常见的拥塞控制算法
    TCP常见的拥塞控制算法有四种，即慢启动（slow-start）、拥塞避免（congestion-avoidance）、快重传（fastretransmit）、快恢复（fastrecovery）。它们的目的是根据网络的拥塞程度动态调整......
  • 转：numpy中expand_dims()函数详解
    注：本文只是本人的通俗理解，有些专业概念表达不是很清楚，但我相信你读完可以理解该函数并会使用。expand_dims(a,axis)中，a为numpy数组，axis为需添加维度的轴，a.shape将在该轴......
  • 【MySQL】substring_index 函数详解
    【MySQL】substring_index函数详解命令格式stringsubstring_index(string<str>,string<separator>,int<count>)命令说明截取字符串str第count个分隔符之前的字......
  • 2023-03-13 递归详解
    1.递归基础和递归的宏观语意本质上，将原来的问题，转化为更小的同一问题举例代码publicclassArrSum{privateintres=0;publicintsum(int[]arr){......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99