强联通分量与Tarjan算法相关

2023-01-02 07:44:27

强联通分量

 在有向图G中，如果两个顶点u，ｖ间有一条从ｕ到ｖ的有向路径，同时还有一条从ｖ到ｕ的有向路径，则称两个顶点强连通。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向非强连通图的极大强连通子图，称为强连通分量强联通分量与Tarjan算法相关

如何求？

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

Tarjan算法 O(N+M)

 

Tarjan算法是基于对dfs的算法，每个强连通分量为搜索树中的一棵子树。

搜索时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。

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

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

void tarjan(int u){
    dfn[u]=low[u]=++idx;
    s[++top]=u;
    is[u]=1;
    for(int i=h[u];i;i=edge[i].nex){
        int v=edge[i].v;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]); 
        }
        else if(is[v])low[u]=min(low[u],dfn[v]);
    } 
    if(low[u]==dfn[u]){
        ++cnt;
        do{
            belong[s[top]]=cnt;
            is[s[top]]=0;
            id[s[top]]=cnt;
            all[cnt]++;
        }while(s[top--]!=u);
    }
}

缩点

将同一个强连通分量中的点缩成同一个新结点，对于两个新结点a,b之间有边相连，当且仅当存在两个点u属于a，v属于b

强联通分量与Tarjan算法相关

例题

 

P1407 [国家集训队]稳定婚姻

题解：

尝试将所有夫妻以男->女方向建图

再将情人关系以女->男方向建图

可以发现出现了一些环，而处在环中的几对夫妻都可以更换伴侣，也就是题目中所说的婚姻不安全。那么我们找出这些环，判断哪些夫妻处在环中即可

对于找环，我们想到了Tarjan求强连通分量，但是这个算法是在有向图上进行的，于是我们尝试给我们连接出的无向图定向，男女交替就可以Tarjan判出环来

#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e5+5;
int n,m,ans,idx,cnt,head[MAXN],dfn[MAXN],low[MAXN];
struct Edge{int to,next;} edge[MAXN];
inline void add_edge(int u,int to)
{edge[++cnt].to=to;edge[cnt].next=head[u];head[u]=cnt;}
int tot,id[MAXN];//tot:强连通分量数目,点i所属强连通分量编号 
stack<int> s;
bool ins[MAXN];
map<string,int> ha;//map存夫妻姓名所对编号,i--i+n 
string girl,boy;
inline void tarjan(int u)
{
    dfn[u]=low[u]=++idx;
    s.push(u);ins[u]=1;//入栈 
    for(int i=head[u];i;i=edge[i].next) {
        int v=edge[i].to;//模板 
        if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
        else if(ins[v]) low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u]) {
        tot++;
        while(s.top()!=u) {
            id[s.top()]=tot;//记录所属强连通分量编号 
            ins[s.top()]=0;//出栈 
            s.pop();
        }
        id[s.top()]=tot;ins[s.top()]=0;s.pop(); 
    }
}
inline int gint()//拙劣的非负快读（据说还有更快的）。 
{
    int ff=1,ee=0;char ss=getchar();
    while(ss<'0'||ss>'9') ss=getchar();
    while(ss>='0'&&ss<='9') {ee=(ee<<1)+(ee<<3)+(ss^48);ss=getchar();}
    return ee*ff;
}
int main()
{
    n=gint();
    for(int i=1;i<=n;i++) cin>>girl>>boy,add_edge((ha[girl]=i),(ha[boy]=i+n));
    m=gint();
    for(int i=1;i<=m;i++) cin>>girl>>boy,add_edge(ha[boy],ha[girl]);
    for(int i=1;i<=n*2;i++) if(!dfn[i]) tarjan(i);//注意n*2 
    for(int i=1;i<=n;i++) if(id[i]==id[i+n]) puts("Unsafe");else puts("Safe");
    return 0;
}

[HAOI2006]受欢迎的牛

题解：

遍历节点时记录下每个点出度 若有两只出度为0则直接判没有（不满足除自己以外所有牛都喜欢自己）

受欢迎的奶牛只有可能是图中唯一的出度为零的强连通分量中的所有奶牛

找出该分量即可

#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e5+5;
int n,m;
struct node{
    int v,nex;
}edge[MAXN];
int tot,h[MAXN];
void add(int u,int v){
   edge[++tot].v=v;
   edge[tot].nex=h[u];
   h[u]=tot; 
}
inline int read() {
    int tmp=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') tmp=(tmp<<1)+(tmp<<3)+ch-'0',ch=getchar();
    return tmp;
}
bool is[MAXN];
int s[MAXN],top;
int cnt,belong[MAXN];
int dfn[MAXN],low[MAXN],idx;
int all[MAXN],id[MAXN];
int du[MAXN]; 
void tarjan(int u){
    dfn[u]=low[u]=++idx;
    s[++top]=u;
    is[u]=1;
    for(int i=h[u];i;i=edge[i].nex){
        int v=edge[i].v;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]); 
        }
        else if(is[v])low[u]=min(low[u],dfn[v]);
    } 
    if(low[u]==dfn[u]){
        ++cnt;
        do{
            belong[s[top]]=cnt;
            is[s[top]]=0;
            id[s[top]]=cnt;
            all[cnt]++;
        }while(s[top--]!=u);
    }
}
int main(){
    n=read();
    m=read();
    for(int i=1;i<=m;i++){
        int u,v;
        u=read();
        v=read();
        add(u,v);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i])tarjan(i);
    }
    for(int w=1;w<=n;w++){
        for(int i=h[w];i;i=edge[i].nex){
            int u=edge[i].v;
            if(id[w]!=id[u]){
                du[id[w]]++;//遍历节点时记录出度 
            }
        }
    }
    int tt=0;
    for(int i=1;i<=cnt;i++)
    if(!du[i]){
        if(tt){
            cout<<0;
            return 0;
        }
    tt=i;
    }
    cout<<all[tt]<<endl;
    return 0;
}

P1455 搭配购买

题解：tarjan+背包

利用tarjan将需要搭配的缩成一个分量

然后将每个分量看做一个物品进行背包

#include<bits/stdc++.h>
using namespace std;
const int maxn=10000+5;
int money[maxn],fa[maxn];
int c[maxn],d[maxn];
int head[maxn],next[maxn],to[maxn],cnt=0;
int add(int x,int y)
{
    to[++cnt]=y;
    next[cnt]=head[x];
    head[x]=cnt;
}
int dfn[maxn],low[maxn],sum=0;
int st[maxn],top=0;
int col=0,co[maxn];
int a[maxn],b[maxn];
int dp[maxn];
void tarjan(int node)
{
    dfn[node]=low[node]=++sum;
    st[++top]=node;
    for(int i=head[node];i;i=next[i])
    {
        int y=to[i];
        if(!dfn[y])
        {
            tarjan(y);
            low[node]=min(low[node],dfn[y]);
        }
        if(!co[y])
        {
            low[node]=min(low[node],low[y]);
        }
    }
    if(dfn[node]==low[node])
    {
        col++;
        while(st[top]!=node)
        {
            a[col]+=c[st[top]];
            b[col]+=d[st[top]];
            co[st[top]]=col;
            top--;
        }
        a[col]+=c[st[top]];
        b[col]+=d[st[top]];
        co[st[top]]=col;
        top--;
    }
}
int main()
{
    int n,m,s;
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&c[i],&d[i]);
    }
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])
        {
            tarjan(i);
        }
    }
    for(int i=1;i<=col;i++)
    {
        for(int j=s;j>=a[i];j--)
        {
            dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
        }
    }
    printf("%d\n",dp[s]);
    return 0;
}

P3388 割点（割顶）

题解：对于根节点 判断是否有两棵及以上的子树

对于非根节点 维护两个数组dfn[]和low[]，dfn[u]表示顶点u第几个被（首次）访问，low[u]表示顶点u及其子树中的点，通过非父子边（回边），能够回溯到的最早的点（dfn最小）的dfn值（但不能通过连接u与其父节点的边）。对于边(u, v)，如果low[v]>=dfn[u]，此时u就是割点。

#include<bits/stdc++.h>
using namespace std;
struct edge{
    int nxt,mark;
}pre[200010];
int n,m,idx,cnt,tot;
int head[100010],DFN[100010],LOW[100010];
bool cut[100010];
void add (int x,int y)
{
    pre[++cnt].nxt=y;
    pre[cnt].mark=head[x];
    head[x]=cnt;
}
void tarjan (int u,int fa)
{
    DFN[u]=LOW[u]=++idx;
    int child=0;
    for (int i=head[u];i!=0;i=pre[i].mark)
    {
        int nx=pre[i].nxt;
        if (!DFN[nx])
        {
            tarjan (nx,fa);
            LOW[u]=min (LOW[u],LOW[nx]);
            if (LOW[nx]>=DFN[u]&&u!=fa)
                cut[u]=1;
            if(u==fa)
                child++;
        }
        LOW[u]=min (LOW[u],DFN[nx]);
    }
    if (child>=2&&u==fa)
        cut[u]=1;
}
int main()
{
    memset (DFN,0,sizeof (DFN));
    memset (head,0,sizeof (head));
    scanf ("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        int a,b;
        scanf ("%d%d",&a,&b);
        add (a,b);
        add (b,a);
    }
    for (int i=1;i<=n;i++)
        if (DFN[i]==0)
            tarjan (i,i);
    for (int i=1;i<=n;i++)
        if (cut[i])
            tot++;
    printf ("%d\n",tot);
    for (int i=1;i<=n;i++)
        if (cut[i])
            printf ("%d ",i);
    return 0;
}
上一篇：洛谷 P4819 [中山市选]杀人游戏（tarjan缩点）


下一篇：【洛谷 3379】最近公共祖先_Tarjan