图论tarjan

有向图的强连通分量

强连通分量：在有向图G中，如果两个顶点vi,vj间有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。
dfn在代表时间戳，而low代表该点可以到达的点的最小dfn值，当low等于dfn的时候，就说明找到了一个强连通分量

code

int n,m,idx,top,cnt;

int dfn[maxn];      //这个点是第几个被访问的
int low[maxn];      //这个点所能到的点的dfn的最小值
bool vis[maxn];     //标记一个点是否在栈中
int s[maxn];        //栈

vector<int> a[maxn];        //图

void tarjan(int u)
{
    dfn[u] = low[u] = ++idx;
    s[++top] = u;
    vis[u] = 1;
    for(auto v : a[u])
    {
        if(!dfn[v])         //如果这个点还没被访问过
        {
            tarjan(v);
            low[u] = min(low[u],low[v]);    //回溯
        }
        else if(vis[v])     //如果这个点在栈内
        {
            low[u] = min(low[u],dfn[v]);
        }
    }
    if(dfn[u] == low[u])        //找到一组强连通分量,而且这一组强连通分量就是从s[top]到s[top]==u;
    {
        cnt++;      //记录强连通分量的个数
        while (s[top] != u)
        {   
            vis[s[top]] = 0;
            top--;
        }
        vis[s[top]] = 0;
        top--;
    }
}

例题

https://www.luogu.com.cn/problem/P2863

无向图的割点和桥

无向连通图中，如果删除某点后，图变成不连通，则称该点为割点
无向连通图中，如果删除某边后，图变成不连通，则称该边为桥

割点

一个顶点u是割点,当且仅当
(1)u为树根，且u有多于一个子树(不然删除这个点，还是联通的)
(2)u不为树根，且存在儿子v，使得dfn[u] <= low[v]

vector<int> a[maxn];        //图

int dfn[maxn];
int low[maxn];
bool cut[maxn];            //是否是割点
int idx;

void tarjan(int u,int fa)        //fa记录最开始的树根
{
    dfn[u]=low[u]=++idx;
    int child = 0;                //根的儿子个数
    for(auto i : a[u])
    {
        if(!dfn[i])
        {
            tarjan(i,fa);
            low[u] = min(low[u],low[i]);
            if(low[i] >= dfn[u] && u != fa) cut[u] = 1;        //u是割点
            if(u == fa) child++;                               //求根节点的子树个数
        }
        low[u] = min(low[u],dfn[i]);
    }
    if(child >= 2 && u == fa) cut[u] = 1;        //u为树根且儿子个数大于等于2
}

桥

一条边(u,v)是桥，当且仅当(u,v)为树枝边，且满足dfn(u) < low(v)（前提是其没有重边）

vector<int> a[maxn];

int dfn[maxn],low[maxn],fa[maxn],idx,ans;

void tarjan(int u,int pre)
{
    dfn[u] = low[u] = ++idx;
    fa[u] = pre;
    for(auto i : a[u])
    {
        if(!dfn[i])
        {
            tarjan(i,u);
            low[u] = min(low[u],low[i]);
            if (low[i] > dfn[u]) ans++;                  //这个是桥
        }
        else if(i != pre)
        {
            low[u] = min(low[u],dfn[i]);
        }
    }
}

参考博客

初探tarjan算法
https://blog.csdn.net/LanQiLi/article/details/85009526