8.18

lyxqqq1 · 2025-08-18 20:54:49 · 个人记录

Tarjan 算法：图论世界的“结构探测者”

在图论和计算机科学领域，Robert Tarjan 发明的 Tarjan 算法是一个高效且用途广泛的基石算法。它主要用于深度优先搜索（DFS） 遍历图的过程中，识别图中关键的结构性元素。其主要作用集中在以下几个方面：

寻找有向图的强连通分量 (Strongly Connected Components - SCCs)
- 核心作用： 这是 Tarjan 算法最著名和最重要的应用。
- 概念： 在有向图中，一个强连通分量是一个最大的顶点子集，其中任意两个顶点 u 和 v 都互相可达（即存在从 u 到 v 的路径，也存在从 v 到 u 的路径）。
- 作用：
  - 理解图的结构： 将复杂的有向图分解成更小的、内部高度互连的 SCCs，是理解和简化图结构的基础。
  - 编译器优化： 在过程间数据流分析和优化中，识别程序调用图的 SCCs 有助于处理递归和循环依赖。
  - 社交网络分析： 识别社交网络中紧密互动的群体（例如，互相关注的用户群）。
  - 网络路由与可靠性： 分析网络拓扑中哪些区域在链路故障时仍能保持内部连通。
  - 电子设计自动化 (EDA)： 分析电路或逻辑门的依赖关系。
  - 解决其他问题的基础： 许多图算法（如求解 2-SAT 问题）需要先将图分解为 SCCs 或在其上进行操作。
寻找无向图的割点 (Articulation Points / Cut Vertices)
- 概念： 割点是无向图中的一个顶点，移除它（及其相连的边）会增加图中连通分量的数量（即图变得“更不连通”）。
- 作用：
  - 网络脆弱性分析： 识别通信网络、交通网络或电力网络中的单点故障关键节点。移除这些节点可能导致网络分裂或服务中断。
  - 图连通性分析： 理解哪些顶点对维持图的整体连通性至关重要。
寻找无向图的桥 (Bridges / Cut Edges)
- 概念： 桥是无向图中的一条边，移除它会增加图中连通分量的数量。
- 作用：
  - 网络脆弱性分析： 识别通信网络、交通网络中的关键链路。断开这些边会直接导致网络分裂。
  - 设计可靠网络： 在设计需要高可靠性的网络（如骨干网）时，避免过度依赖桥接边，或为它们设计冗余备份。

题目号	时间复杂度	空间复杂度	思路
A	O（n+m）	O（n）	割点模板题
B	O（n+m）	O（n）	割边模板题
C	O（n+m）	O（n）	点双模板题
D	O（n+m）	O（n）	割点改编题
G	O（∑(2^n+n^3)）	O（n）	tarjan的变形

下面附上ACcode： A、

#include<bits/stdc++.h>
using namespace std;
int tot,n,m,x,y,dfn[20005],low[20005],ans[100005],ans1;
vector<int>l[100005];
void dfs(int u,int fa)
{
    dfn[u]=low[u]=++tot;
    int flag=0,son=0;
    for(int i=0;i<l[u].size();i++)
    {
        int v=l[u][i];
        if(dfn[v])
        {
            low[u]=min(low[u],dfn[v]);
        }
        else
        {
            son++;
            dfs(v,u);
            low[u]=min(low[u],low[v]);
            if(!flag and low[v]>=dfn[u] and fa!=u)
            {
                ans[++ans1]=u;
                flag=1;
            }
        }
    }
    if(!flag and fa==u and son>1)
    {
        ans[++ans1]=u;
    }
} 
signed main()
{
    cin>>n>>m;
    while(m--)
    {
        cin>>x>>y;
        l[x].push_back(y);
        l[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i])
            dfs(i,i);
    sort(ans+1,ans+ans1+1);
    cout<<ans1<<endl;
    for(int i=1;i<=ans1;i++)
        cout<<ans[i]<<" ";
    return 0;
}

B、

#include<bits/stdc++.h>
using namespace std;
struct N{
    int x,y;
};
int tot,n,m,x,y,dfn[20005],low[20005];
N ans[100005];
int ans1;
vector<int>l[100005];
void dfs(int u,int fa)
{
    dfn[u]=low[u]=++tot;
    int flag=0,son=0;
    for(int i=0;i<l[u].size();i++)
    {
        int v=l[u][i];
        if(v==fa)
            continue;
        if(dfn[v])
        {
            low[u]=min(low[u],dfn[v]);
        }
        else
        {
            son++;
            dfs(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u])
            {
                ans[++ans1].x=u;
                ans[ans1].y=v;
            }
        }
    }
} 
int cmp(N x,N y)
{
    if(x.x!=y.x)
        return x.x<y.x;
    return x.y<y.y;
}
signed main()
{
    cin>>n>>m;
    while(m--)
    {
        cin>>x>>y;
        l[x].push_back(y);
        l[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i])
            dfs(i,i);
    sort(ans+1,ans+ans1+1,cmp);
    for(int i=1;i<=ans1;i++)
        cout<<ans[i].x<<" "<<ans[i].y<<"\n";
    return 0;
}

C、

#include<bits/stdc++.h>
using namespace std;
int n,m,low[500005],dfn[500005],ans1,cnt;
int nxt[4000005],head[500005],go[4000005],k;
vector<int>ans[500005];
stack<int>s;
void add(int u,int v)
{
    nxt[++k]=head[u];
    head[u]=k;
    go[k]=v;
}
void dfs(int u,int fa)
{
    dfn[u]=low[u]=++cnt;
    if(u==fa&&!head[u])
    {
        ans[++ans1].push_back(u);
    }
    s.push(u);
    int i=head[u];
    while(i)
    {
        int g=go[i];
        if(!dfn[g])
        {
            dfs(g,fa);
            low[u]=min(low[u],low[g]);
            if(low[g]>=dfn[u])
            {
                ans1++;
                int p;
                do{
                    p=s.top();
                    s.pop();
                    ans[ans1].push_back(p);
                }while(p!=g);
                ans[ans1].push_back(u);
            }
        }
        else
            low[u]=min(low[u],dfn[g]);
        i=nxt[i];
    }
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        if(x==y) continue;
        add(x,y);
        add(y,x);
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i]) dfs(i,i);
    }
    cout<<ans1<<endl;
    for(int i=1;i<=ans1;i++)
    {
        cout<<ans[i].size()<<" ";
        for(int j=0;j<ans[i].size();j++)
        cout<<ans[i][j]<<" ";
        cout<<endl;
    }
}

D、

#include<bits/stdc++.h>
using namespace std;
int tot,n,m,x,y,a,b,dfn[200005],low[200005],ans[200005],ans1;
vector<int>l[200005];
void dfs(int u)
{
    dfn[u]=low[u]=++tot;
    for(int i=0;i<l[u].size();i++)
    {
        int v=l[u][i];
        if(dfn[v])
        {
            low[u]=min(low[u],dfn[v]);
        }
        else
        {
            dfs(v);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u] and a!=u and dfn[b]>=dfn[v])
            {
                ans[u]=1;
            }
        }
    }
} 
signed main()
{
    cin>>n;
    while(cin>>x>>y)
    {
        if(x==y and x==0)
            break;
        l[x].push_back(y);
        l[y].push_back(x);
    }
    cin>>a>>b;
    dfs(a);
    for(int i=1;i<=n;i++)
    {
        if(ans[i])
        {
            cout<<i<<endl;
            return 0;
        }
    }
    cout<<"No solution"<<endl;
    return 0;
}

G、

#include<bits/stdc++.h>
using namespace std;
int t,n,m,ans,vis[200005],u,v,w[200005],sum[200005],d;
vector<int>l[200005];
void dfs(int u,int fa)
{
    vis[u]=1;
    for(int i=0;i<l[u].size();i++)
    {
        if(l[u][i]==fa)
            continue;
        if(vis[l[u][i]])
        {
            if(ans==0)
                ans=1,w[u]=1;
        }
        else
        {
            dfs(l[u][i],u);
        }
    }
}
void dfs2(int u,int v)
{
    vis[u]=1;
    w[u]=max(w[u],v);
    for(int i=0;i<l[u].size();i++)
    {
        if(!vis[l[u][i]])
        {
            dfs2(l[u][i],max(v,w[u]));
        }
    }
}
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        ans=0;
        for(int i=1;i<=n;i++)
            l[i].clear();
        for(int i=1;i<=n;i++)
            vis[i]=w[i]=0;
        for(int i=1;i<=m;i++)
        {
            cin>>u>>v;
            l[u].push_back(v);
            l[v].push_back(u);
        }d=0;   
        dfs(1,0);
        int flag=0;
        for(int i=1;i<=n;i++)
            if(vis[i]==0||ans==0)
            {
                flag=1;
                cout<<-1<<"\n";
                break;
            }
        if(flag)
            continue;
        for(int i=1;i<=n;i++)
            vis[i]=0;dfs2(1,0);
        for(int i=1;i<=n;i++)
        {
            if(w[i])
                cout<<"B";
            else 
                cout<<"W";
        }
        cout<<endl;
    }
}