图论算法-Tarjan模板 【缩点;割顶;双连通分量】
为小伙伴们总结的Tarjan三大算法
Tarjan缩点(求强连通分量)
int n;
int low[100010],dfn[100010];
bool ins[100010];
int col[100010];//记录每个点所属强连通分量(即染色)
vector<int> map[100010];
stack<int> st;
int tot;//时间戳
int colnum;//记录强连通分量个数
void tarjan(int u)
{
low[u]=dfn[u]=++tot;
st.push(u);
ins[u]=true;
for(int j=0;j<map[u].size();j++)
{
int v=map[u][j];
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])
{
//到这里即发现了一个新的强连通分量
colnum++;
int temp;
int cont=0;
do
{
temp=st.top();
st.pop();
ins[temp]=false;
//将同一强连通分量的点染色,表示一个缩点
col[temp]=colnum;
//在这里也可以对该强连通分量进行一些其他操作
//例如保存该缩点所包含的原节点
}
while(temp!=u);
}
}
void init()
{
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(col,0,sizeof(col));
memset(ins,false,sizeof(ins));
tot=colnum=0;
}
void solve()
{
init();
for(int i=1;i<=n;i++)
{
if(!dfn[i])
tarjan(i);
}
}
Tarjan求割点(割顶)
int n;
vector<int> map[100010];
int low[100010],dfn[100010];
bool cut[1000010];//记录割点
int tot;
void tarjan(int u,int fa)
{
low[u]=dfn[u]=++tot;
int child=0;
for(int j=0;j<map[u].size();j++)
{
int v=map[u][j];
if(!dfn[v])
{
child++;
tarjan(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u])
cut[u]=true;
}
else if(dfn[v]<dfn[u]&&v!=fa)
low[u]=min(low[u],dfn[v]);
}
if(fa<0&&child==1)
cut[u]=false;
}
void init()
{
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(cut,false,sizeof(cut));
tot=0;
}
void solve()
{
init();
for(int i=1;i<=n;i++)
{
if(!dfn[i])
tarjan(i,-1);
//**高亮**这里的第二个参数一定要设为负数
}
//cut[i]==true即表示i为割点
}
Tarjan求点-双连通分量
int n;
vector<int> map[100010];
int low[100010],dfn[100010];
bool cut[1000010];
int bcc[1000010];
int tot;
int bcc_cont//记录双连通分量个数;
struct edge{int u,v};
stack<edge> E;
void tarjan(int u,int fa)
{
low[u]=dfn[u]=++tot;
int child=0;
for(int j=0;j<map[u].size();j++)
{
int v=map[u][j];
edge e=(edge) {u,v};
if(!dfn[v])
{
E.push(e);
child++;
tarjan(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u])
{
//到这里即发现了一个新的双连通分量
cut[u]=true;
bcc_cont++:
while(1)
{
edge temp=E.top();
E.pop();
if(bccno[temp.u]!=bcc_cont)
bccno[temp.u]=bcc_cont;
if(bccno[temp.v]!=bcc_cont)
bccno[temp.v]=bcc_cont;
if(temp.u==u&&temp.v==v)
break;
}
}
}
else if(dfn[v]<dfn[u]&&v!=fa)
{
E.push(e);
low[u]=min(low[u],dfn[v]);
}
}
if(fa<0&&child==1)
cut[u]=false;
}
void init()
{
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(bccno,0,sizeof(bccno));
tot=bcc_cont=0;
}
void solve()
{
init();
for(int i=1;i<=n;i++)
{
if(!dfn[i])
tarjan(i,-1);//**高亮**这里的第二个参数一定要设为负数
}
}
其实三个算法思路都基本一致
毕竟都是同一个人提出的嘛
图论算法-Tarjan模板 【缩点;割顶;双连通分量】的更多相关文章
-
Tarjan算法应用 (割点/桥/缩点/强连通分量/双连通分量/LCA(最近公共祖先)问题)(转载)
Tarjan算法应用 (割点/桥/缩点/强连通分量/双连通分量/LCA(最近公共祖先)问题)(转载) 转载自:http://hi.baidu.com/lydrainbowcat/blog/item/2 ...
-
tarjan算法求无向图的桥、边双连通分量并缩点
// tarjan算法求无向图的桥.边双连通分量并缩点 #include<iostream> #include<cstdio> #include<cstring> ...
-
Tarjan应用:求割点/桥/缩点/强连通分量/双连通分量/LCA(最近公共祖先)【转】【修改】
一.基本概念: 1.割点:若删掉某点后,原连通图分裂为多个子图,则称该点为割点. 2.割点集合:在一个无向连通图中,如果有一个顶点集合,删除这个顶点集合,以及这个集合中所有顶点相关联的边以后,原图变成 ...
-
(转)Tarjan应用:求割点/桥/缩点/强连通分量/双连通分量/LCA(最近公共祖先)
基本概念: 1.割点:若删掉某点后,原连通图分裂为多个子图,则称该点为割点. 2.割点集合:在一个无向连通图中,如果有一个顶点集合,删除这个顶点集合,以及这个集合中所有顶点相关联的边以后,原图变成多个 ...
-
tarjan求桥、割顶
若low[v]>dfn[u],则(u,v)为割边.但是实际处理时我们并不这样判断,因为有的图上可能有重边,这样不好处理.我们记录每条边的标号(一条无向边拆成的两条有向边标号相同),记录每个点的父 ...
-
图论--割边--Tarjan模板
#include<iostream> #include<stdio.h> #include<vector> using namespace std; const i ...
-
图论--割点--Tarjan模板
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> ...
-
[Tarjan系列] Tarjan算法求无向图的双连通分量
这篇介绍如何用Tarjan算法求Double Connected Component,即双连通分量. 双联通分量包括点双连通分量v-DCC和边连通分量e-DCC. 若一张无向连通图不存在割点,则称它为 ...
-
点/边 双连通分量---Tarjan算法
运用Tarjan算法,求解图的点/边双连通分量. 1.点双连通分量[块] 割点可以存在多个块中,每个块包含当前节点u,分量以边的形式输出比较有意义. typedef struct{ //栈结点结构 保 ...
随机推荐
-
《DSP using MATLAB》示例Example5.15
代码: x1 = [1,2,2]; x2 = [1,2,3,4]; y1 = circonvt(x1,x2,5); % N = 5 n1 = 0:1:length(x1)-1; n2 = 0:1:le ...
-
ORA-01033: ORACLE 正在初始化或关闭 进程 ID: 0 会话 ID: 0 序列号: 0
用了很长时间的数据库,一直都挺好,今天早上一来报这个错,开始追究原因. 1.用SYS用户登录: 2.将数据库修改为打开状态,alter database open,出现如下的错误提示: ORA-160 ...
-
Linux大文件分割split和合并cat使用方法
本文主要介绍linux下两个命令:split和cat.其中,相信大家都熟悉cat命令,一般用来查看一个文件的内容,但是它还其它的功能,比如这里要介绍的文件合并功能,它可把多个文件内容合并到一个文件中. ...
-
uvalive 3263 That Nice Euler Circuit
题意:平面上有一个包含n个端点的一笔画,第n个端点总是和第一个端点重合,因此团史一条闭合曲线.组成一笔画的线段可以相交,但是不会部分重叠.求这些线段将平面分成多少部分(包括封闭区域和无限大区域). 分 ...
-
qt5 基础知识
QWidget wQLineEdit edit; edit.show(); //如果没有这句,编辑框edit将会显示在父窗口的左上角edit.setParent(&w); //以w为父窗口并显 ...
-
Vue 非父子组件通信
组件是Vue核心的一块内容,组件之间的通信也是很基本的开发需求.组件通信又包括父组件向子组件传数据,子组件向父组件传数据,非父子组件间的通信.前两种通信Vue的文档都说的很清楚,但是第三种文档上确只有 ...
-
Matlab绘图基础——绘制向量图,二维三维(绘制参数曲线图)
------------------------------------------- %绘制向量场图 %例一 clear all;clc; [X,Y] = meshgrid(-2:.2:2,-3:. ...
-
使用synchronized wait() notifyall() 实现简单的加减法同步 竞争抢答
import java.util.concurrent.Callable; import java.util.concurrent.ExecutionException; import java.co ...
-
unity, do nothing的state
要想在animator的stateMachine中建一个"doNothing",要注意:为了保证"doNothing"state能正常运转,不被无故跳过, Mo ...
-
HDU 1263 二维map
题意:给出一份水果的交易表,根据地区统计出水果的交易情况. 思路:二维map使用. #include<cstdio> #include<string> #include ...