图论算法-Tarjan模板 【缩点;割顶;双连通分量】

时间:2023-01-09 13:24:17

图论算法-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模板 【缩点;割顶;双连通分量】的更多相关文章

  1. Tarjan算法应用 (割点&sol;桥&sol;缩点&sol;强连通分量&sol;双连通分量&sol;LCA&lpar;最近公共祖先&rpar;问题)(转载)

    Tarjan算法应用 (割点/桥/缩点/强连通分量/双连通分量/LCA(最近公共祖先)问题)(转载) 转载自:http://hi.baidu.com/lydrainbowcat/blog/item/2 ...

  2. tarjan算法求无向图的桥、边双连通分量并缩点

    // tarjan算法求无向图的桥.边双连通分量并缩点 #include<iostream> #include<cstdio> #include<cstring> ...

  3. Tarjan应用&colon;求割点&sol;桥&sol;缩点&sol;强连通分量&sol;双连通分量&sol;LCA&lpar;最近公共祖先&rpar;【转】【修改】

    一.基本概念: 1.割点:若删掉某点后,原连通图分裂为多个子图,则称该点为割点. 2.割点集合:在一个无向连通图中,如果有一个顶点集合,删除这个顶点集合,以及这个集合中所有顶点相关联的边以后,原图变成 ...

  4. &lpar;转&rpar;Tarjan应用&colon;求割点&sol;桥&sol;缩点&sol;强连通分量&sol;双连通分量&sol;LCA&lpar;最近公共祖先&rpar;

    基本概念: 1.割点:若删掉某点后,原连通图分裂为多个子图,则称该点为割点. 2.割点集合:在一个无向连通图中,如果有一个顶点集合,删除这个顶点集合,以及这个集合中所有顶点相关联的边以后,原图变成多个 ...

  5. tarjan求桥、割顶

    若low[v]>dfn[u],则(u,v)为割边.但是实际处理时我们并不这样判断,因为有的图上可能有重边,这样不好处理.我们记录每条边的标号(一条无向边拆成的两条有向边标号相同),记录每个点的父 ...

  6. 图论--割边--Tarjan模板

    #include<iostream> #include<stdio.h> #include<vector> using namespace std; const i ...

  7. 图论--割点--Tarjan模板

    #include <iostream> #include <algorithm> #include <cstdio> #include <cstring&gt ...

  8. &lbrack;Tarjan系列&rsqb; Tarjan算法求无向图的双连通分量

    这篇介绍如何用Tarjan算法求Double Connected Component,即双连通分量. 双联通分量包括点双连通分量v-DCC和边连通分量e-DCC. 若一张无向连通图不存在割点,则称它为 ...

  9. 点&sol;边 双连通分量---Tarjan算法

    运用Tarjan算法,求解图的点/边双连通分量. 1.点双连通分量[块] 割点可以存在多个块中,每个块包含当前节点u,分量以边的形式输出比较有意义. typedef struct{ //栈结点结构 保 ...

随机推荐

  1. 《DSP using MATLAB》示例Example5&period;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 ...

  2. ORA-01033&colon; ORACLE 正在初始化或关闭 进程 ID&colon; 0 会话 ID&colon; 0 序列号&colon; 0

    用了很长时间的数据库,一直都挺好,今天早上一来报这个错,开始追究原因. 1.用SYS用户登录: 2.将数据库修改为打开状态,alter database open,出现如下的错误提示: ORA-160 ...

  3. Linux大文件分割split和合并cat使用方法

    本文主要介绍linux下两个命令:split和cat.其中,相信大家都熟悉cat命令,一般用来查看一个文件的内容,但是它还其它的功能,比如这里要介绍的文件合并功能,它可把多个文件内容合并到一个文件中. ...

  4. uvalive 3263 That Nice Euler Circuit

    题意:平面上有一个包含n个端点的一笔画,第n个端点总是和第一个端点重合,因此团史一条闭合曲线.组成一笔画的线段可以相交,但是不会部分重叠.求这些线段将平面分成多少部分(包括封闭区域和无限大区域). 分 ...

  5. qt5 基础知识

    QWidget wQLineEdit edit; edit.show(); //如果没有这句,编辑框edit将会显示在父窗口的左上角edit.setParent(&w); //以w为父窗口并显 ...

  6. Vue 非父子组件通信

    组件是Vue核心的一块内容,组件之间的通信也是很基本的开发需求.组件通信又包括父组件向子组件传数据,子组件向父组件传数据,非父子组件间的通信.前两种通信Vue的文档都说的很清楚,但是第三种文档上确只有 ...

  7. Matlab绘图基础——绘制向量图,二维三维(绘制参数曲线图)

    ------------------------------------------- %绘制向量场图 %例一 clear all;clc; [X,Y] = meshgrid(-2:.2:2,-3:. ...

  8. 使用synchronized wait&lpar;&rpar; notifyall&lpar;&rpar; 实现简单的加减法同步 竞争抢答

    import java.util.concurrent.Callable; import java.util.concurrent.ExecutionException; import java.co ...

  9. unity&comma; do nothing的state

    要想在animator的stateMachine中建一个"doNothing",要注意:为了保证"doNothing"state能正常运转,不被无故跳过, Mo ...

  10. HDU 1263 二维map

    题意:给出一份水果的交易表,根据地区统计出水果的交易情况.   思路:二维map使用.   #include<cstdio> #include<string> #include ...