专栏文章

8.18

llyxqqq1
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio9ac0q
此快照首次捕获于
2025/12/02 15:27
3 个月前
此快照最后确认于
2025/12/02 15:27
3 个月前
查看原文

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

在图论和计算机科学领域，Robert Tarjan 发明的 Tarjan 算法是一个高效且用途广泛的基石算法。它主要用于深度优先搜索（DFS） 遍历图的过程中，识别图中关键的结构性元素。其主要作用集中在以下几个方面：
  1. 寻找有向图的强连通分量 (Strongly Connected Components - SCCs)
    • 核心作用： 这是 Tarjan 算法最著名和最重要的应用。
    • 概念： 在有向图中，一个强连通分量是一个最大的顶点子集，其中任意两个顶点 u 和 v 都互相可达（即存在从 u 到 v 的路径，也存在从 v 到 u 的路径）。
    • 作用：
      • 理解图的结构： 将复杂的有向图分解成更小的、内部高度互连的 SCCs，是理解和简化图结构的基础。
      • 编译器优化： 在过程间数据流分析和优化中，识别程序调用图的 SCCs 有助于处理递归和循环依赖。
      • 社交网络分析： 识别社交网络中紧密互动的群体（例如，互相关注的用户群）。
      • 网络路由与可靠性： 分析网络拓扑中哪些区域在链路故障时仍能保持内部连通。
      • 电子设计自动化 (EDA)： 分析电路或逻辑门的依赖关系。
      • 解决其他问题的基础： 许多图算法（如求解 2-SAT 问题）需要先将图分解为 SCCs 或在其上进行操作。
  2. 寻找无向图的割点 (Articulation Points / Cut Vertices)
    • 概念： 割点是无向图中的一个顶点，移除它（及其相连的边）会增加图中连通分量的数量（即图变得“更不连通”）。
    • 作用：
      • 网络脆弱性分析： 识别通信网络、交通网络或电力网络中的单点故障关键节点。移除这些节点可能导致网络分裂或服务中断。
      • 图连通性分析： 理解哪些顶点对维持图的整体连通性至关重要。
  3. 寻找无向图的桥 (Bridges / Cut Edges)
    • 概念： 桥是无向图中的一条边，移除它会增加图中连通分量的数量。
    • 作用：
      • 网络脆弱性分析： 识别通信网络、交通网络中的关键链路。断开这些边会直接导致网络分裂。
      • 设计可靠网络： 在设计需要高可靠性的网络（如骨干网）时，避免过度依赖桥接边，或为它们设计冗余备份。
题目号时间复杂度空间复杂度思路
AO（n+mn+m）O（nn）割点模板题
BO（n+mn+m）O（nn）割边模板题
CO（n+mn+m）O（nn）点双模板题
DO（n+mn+m）O（nn）割点改编题
GO（∑(2n+n3)∑(2^n+n^3)）O（nn）tarjan的变形
下面附上ACcode： A、
CPP
#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、
CPP
#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、
CPP
#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、
CPP
#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、
CPP
#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;
	}
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...