图的Tarjan算法
2024-10-19 07:14:32
“Tarjan有三种算法 你们知道吗”——Tar乙己
void tarjan(int x)
{
low[x]=dfn[x]=++ind;
q[++top]=x;mark[x]=;
for(int i=last[x];i;i=e[i].next)
if(!dfn[e[i].to])
{
tarjan(e[i].to);
low[x]=min(low[x],low[e[i].to]);
}
else if(mark[e[i].to])
low[x]=min(low[x],dfn[e[i].to]);
if(low[x]==dfn[x])
{
int now=;scc++;
while(now!=x)
{
now=q[top--];mark[now]=;
bl[now]=scc;num[scc]++;
}
}
}
缩点
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<vector>
using namespace std;
const int maxn=;
int first[maxn],to[maxn],next[maxn],cnt,from[maxn];
void add(int u,int v)
{
from[++cnt]=u;
to[cnt]=v;
next[cnt]=first[u];
first[u]=cnt;
}
int dfn[maxn],low[maxn],vis[maxn],ind,scc,now,st[maxn],top;
int isc[maxn];
vector<int> bl[maxn];
int blc;
int tag[maxn];
void Tarjan_dfs(int x,int fa)
{
int son=;
low[x]=dfn[x]=++ind;
for(int i=first[x];i;i=next[i])
{
int now=to[i];
if(!dfn[now])
{
st[++top]=i;son++;
Tarjan_dfs(now,x);
low[x]=min(low[x],low[now]);
if(low[now]>=dfn[x])
{
isc[x]=;
bl[++blc].clear();
while()
{
int num=st[top--];
if(tag[from[num]]!=blc)
{
bl[blc].push_back(from[num]);
tag[from[num]]=blc;
}
if(tag[to[num]]!=blc)
{
bl[blc].push_back(to[num]);
tag[to[num]]=blc;
}
if(to[num]==now && from[num]==x)break;
}
}
}
else if(dfn[now]<dfn[x] && now!=fa)
{
st[++top]=i;
low[x]=min(low[x],dfn[now]);
}
}
if(fa== && son==)isc[x]=;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
for(int i=;i<=n;i++)if(!dfn[i])Tarjan_dfs(i,-);
cout<<blc<<endl;
return ;
}
点双连通分量
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<vector>
using namespace std;
const int maxn=;
int first[maxn],to[maxn],next[maxn],cnt,from[maxn];
void add(int u,int v)
{
from[++cnt]=u;
to[cnt]=v;
next[cnt]=first[u];
first[u]=cnt;
}
int dfn[maxn],low[maxn],vis[maxn],ind,scc,now,st[maxn],top;
int isb[maxn];
vector<int> bl[maxn];
int blc;
int tag[maxn];
void Tarjan_dfs(int x,int fa)
{
dfn[x]=low[x]=++ind;
for(int i=first[x];i;i=next[i])
{
int v=to[i];
if(!dfn[v])
{
Tarjan_dfs(v,x);
low[x]=min(low[x],low[v]);
if(low[v]>dfn[x])
isb[i]=isb[i^]=;
}
else if(dfn[v]<dfn[x] && v!=fa)low[x]=min(low[x],dfn[v]);
}
}
int vis[maxn];
void dfs(int x)
{
vis[x]=;
tag[x]=blc;
for(int i=first[x];i;i=next[i])
{
int v=to[i];
if(isb[v])continue;
if(!vis[i])dfs(v);
}
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
for(int i=;i<=n;i++)if(!dfn[i])Tarjan_dfs(i,-);
for(int i=;i<=n;i++)if(!vis[i]){blc++;dfs(i);}
cout<<blc<<endl;
return ;
}
边双连通分量
最新文章
- C# 对多个文件进行zip压缩
- [译] Closures in Lua - Lua中的闭包
- 指令发email
- Swift - 05 - 数值型字面量
- Ajax制作无刷新评论系统
- vs2013 MVC 无法确定要使用哪一版本的 ASP.NET Web Pages错误
- GitLab 安装配置笔记(转)
- C语言高效位操作
- 【C++】bazel的使用
- Let&#39;s Encrypt,免费好用的 HTTPS 证书
- TypeScript: Week Reflection
- Ext.grid.panel 改变某一行的字体颜色
- springcloud的turbine集成zookeeper
- copy之深浅拷贝
- 005-Python字典
- grails2.3.3发布了-【grails】
- 洛谷.1333.瑞瑞的木棍(欧拉路径 Hash)
- Json.Net 在.Net Core 2.0 中序列化DataSet 问题
- ios -RunTi me(相关知识)
- C语言变量的声明位置
热门文章
- Java多态案例分析
- mysql慢查询日志分析工具(python写的)
- EhCache 集群 配置(RMI方式)
- POJ 1113 Wall【凸包周长】
- LOJ#10064. 「一本通 3.1 例 1」黑暗城堡
- Java &; 混型
- SAP初始账号
- eclipse---个人设置
- centos 6.5 编译安装了 Nginx1.6.0+MySQL5.6.19+PHP5.5.14
- IOS int NSInteger NSNumber区分