Tarjan求强连通分量，割点，桥，和缩点。

Tarjan

Tarjan，全名Robert Tarjan，美国计算机科学家，创造了很多算法。

Tarjan算法就是以他命名的，可求解强连通分量、割点和桥。

强连通分量

有向图强连通分量：在有向图G中，如果两个顶点vi,vj间（vi>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量(strongly connected components)。

求解强连通分量、割点、桥的Tarjan算法都差不多，都是通过DFS来找的。

在Tarjan算法中，有几个非常重要的变量。

dfn[i] : 表示第i个顶点在dfs中第几个访问（时间戳）

low[i] : 表示第i个顶点可以回溯到的最早访问的顶点

sta : 一个栈表示当前所有可能能构成是强连通分量的点

ins[i] : 表示第i个顶点是否在栈内

当然很难懂先看伪代码：

void Tarjan(int u):
	low[u] = dfn[u] = ++ind;
	ins[u] = 1;
	stack.push(i);
	for v in <u, v>:
	    if(v is not visited):
	        Tarjan(v)
	        low[u] = min(low[u], low[v]);
	    else if(v in stack):
	        low[u] = min(low[u], dfn[v]);
	
	//表示这是一个强连通分量
	if(low[u] == dfn[u]):
	    int p;
	    cnt++;
	    do:
	        p = stack.top;
	        stack.pop;
	        ins[p] = 0;
	        belong[p] = cnt;
	    while(p != u)

当然这伪代码一点也不伪，还是先看看图解吧（图解是参考别人的，嘻嘻）

以这有向图为例

Tarjan求强连通分量，割点，桥，和缩点。

然后从顶点1开始dfs来到下图：

Tarjan求强连通分量，割点，桥，和缩点。

然后到了顶点5的时候不能到dfs其他点了，并且并且low[5] = dfn[5]，说明存在强连通分量。把栈中的元素依次出栈，直到遇到了顶点5。这里只出栈了顶点5，说明顶点5单独成为一个强连通分量。

此时dfs回退到顶点3

Tarjan求强连通分量，割点，桥，和缩点。

此时顶点3和顶点5的情况一样，顶点3单独成为一个强连通分量.

回退到顶点2，继续dfs到顶点4

Tarjan求强连通分量，割点，桥，和缩点。

这时候顶点4，dfs到顶点1，发现顶点1已经遍历过了，所以更新顶点4的low为1.

Tarjan求强连通分量，割点，桥，和缩点。

顶点4dfs完了，回退到顶点2，更新顶点2的low = 1，然后回退到顶点1。顶点1也结束了dfs了，并且low[1] = dfn[1]。说明有一个强连通分量。依次退栈直到得到顶点1.

这时候顶点1、 2、 4成为一个强连通分量。

Tarjan求强连通分量，割点，桥，和缩点。

好了，算法就结束了。

模板如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
typedef pair<int, int> P;
const int maxn = 5e5+5;
const ll mod = 1e9+7;

using namespace std;
vector<int> g[maxn];
int low[maxn], dfn[maxn], sta[maxn], ins[maxn], belong[maxn];//belong是说明他是哪个点的强连通分量
int cnt, ind, tot; //cnt：强连通分量的数量， ind：时间戳， tot：sta的top

void init()
{
    memset(ins, 0, sizeof(ins));
    memset(belong, 0, sizeof(belong));
    memset(dfn, 0, sizeof(dfn));
    cnt = ind = tot = 0;
}
//求强连通分量
void Tarjan(int u)
{
    low[u] = dfn[u] = ++ind;
    ins[u] =1;
    sta[++tot] = u;
    for(int i=0;i<g[u].size();i++)
    {
        int v = g[u][i];
        if(!dfn[v])
        {
            Tarjan(v);
            low[u] = min(low[u],low[v]);
        }
        else if(ins[v])
        {
            low[u] = min(low[u],low[v]);
        }
    }
    int p;
    if(low[u] == dfn[u])
    {
        ++cnt;
        do
        {
            p = sta[tot--];
            belong[p] = cnt;
            ins[p] = 0;
        }while(p!=u);
    }

}

/*
5 5
1 2
2 3
2 4
3 5
4 1
*/
int main()
{

    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
    }
    init();
    //依次tarjan，就可以避免输入的图不是连通图的情况，若只tarjan（1），非连通图有误。
    for (int i=1;i<=n;i++)
        if (!dfn[i]) Tarjan(i);

    for(int i=1;i<=n;i++)
        cout<<belong[i]<<" ";
    return 0;
}

输入上面图解的例子，可得：

Tarjan求强连通分量，割点，桥，和缩点。

割点

在一个无向图中，如果删除一个顶点及与它相关联的边之后，图的连通分量增多了，则称这一个点为割点。

判断是否割点有两种情况：

1.对于根节点来说，只要它至少有两颗子树，那么根节点一定是割点。对于其它顶点来说则麻烦一些。

2.回想一下Tarjan算法中low的意义，表示该顶点能够回溯到最早访问的顶点的序号。对于一个顶点来说，在它之前访问的一个顶点是该顶点的父亲，在它父亲之前的是它的祖先，若该顶点能够不通过父亲就回溯到祖先的话，那么说明该顶点的父亲不是割点。所以，若一个顶点的所有儿子都能够不通过它自己就能回溯到祖先顶点，则该顶点不是割点，否则就是割点。

所以对于边<u, v>来说，若low[v] >= dfn[u]，则u是割点。

Tarjan求强连通分量，割点，桥，和缩点。

对于上图来说，如果是2和3是割点。

模板如下：

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<stdlib.h>
#include<string>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define IO ios::sync_with_stdio(0)
typedef pair<int, int> P;
const int maxn = 2e5+5;
const ll mod = 1e9+7;
using namespace std;

vector<int> g[maxn];
// iscut[i]: 若顶点i是割点，则为1，反之为0
int low[maxn], dfn[maxn], iscut[maxn];
int ind;
int ans= 0 ;
void init()
{
    memset(dfn, 0, sizeof(dfn));
    memset(iscut, 0, sizeof(iscut));
    ind = 0;
}

// pa为u的父节点，初始时Tarjan(i, i)
void Tarjan(int u, int pa)
{
    int cnt = 0; //用来记录子树的数量
    low[u] = dfn[u] = ++ind;
    for(int i=0;i<g[u].size();i++)
    {
        int v = g[u][i];
        if(!dfn[v])//未被访问过
        {
            Tarjan(v, u);
            low[u] = min(low[u], low[v]);
            // 若low[v]>=dfn[u]，并且u不是根节点，则u是割点
            if(low[v] >= dfn[u] && pa!=u)
                iscut[u] = 1;
            // 若u是根节点，则cnt++
            if(u == pa)
                cnt++;
        }
        //else if(v != pa) //若v不等于父节点
            low[u] = min(low[u], dfn[v]);
    }
    if(cnt>=2 && u==pa) //根节点子树数量大于等于2，则为割点
        iscut[u] = 1;
}
/*
5 5
1 2
2 3
2 4
3 5
4 1
*/
int main()
{

    IO;
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    init();
    for(int i=1;i<=n;i++)
        if(dfn[i]==0)
            Tarjan(i,i);
    for(int i=1;i<=n;i++)
        if(iscut[i]) ans++;
    cout<<ans<<endl;

    for(int i=1;i<=n;i++)
        if(iscut[i])
            cout<<i<<" ";
    return 0;
}

桥

桥也叫割边，对于边e来说，若去掉了e，图的连通分量增多了，则说明e为桥。

找割边和找割点类似。对于边<u, v>来说，若low[v] > dfn[u]，则<u, v>是桥。

Tarjan求强连通分量，割点，桥，和缩点。

所以上图，边<2, 3>和<3, 5>都是桥。

模板：待补充。

此外，tarjan还可以用来缩点。

Tarjan缩点

缩点一般用于有向图，简单来说就是：把图中的一个强联通分量直接缩成一个点

Tarjan缩点之后，图就变成了有向无环图（DAG），大致可以想象成单一有向的线性序列，比如

Tarjan求强连通分量，割点，桥，和缩点。

然后DAG图的一些性质：

性质（结合上面这个DAG图）：

①如果超级点入度为0，并且图中只有一个入度为0的超级点，那么显然他可以到达其他任何点，而不能被任何点到达。

②如果超级点出度为0，并且图中只有一个出度为0的超级点，那么显然他可以被任何其他点到达，而不能到达任何点

也是这类题目的一些解题思路了

而上面图解中的例子

Tarjan求强连通分量，割点，桥，和缩点。

就可以缩成这样的图：

Tarjan求强连通分量，割点，桥，和缩点。

也可以缩成这样:

Tarjan求强连通分量，割点，桥，和缩点。

这种重新构图，从1开始标点，当然了要看具体题目的情况。

这里给出，洛谷P3387【模板】缩点的题解，就不要在意一些傻逼注释…

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
typedef pair<int, int> P;
const int maxn = 1e5+5;
const ll mod = 1e9+7;
#define IO ios::sync_with_stdio(0)
using namespace std;
vector<int> g[maxn];
int val[maxn],low[maxn], dfn[maxn], sta[maxn], ins[maxn], belong[maxn];
int cnt, ind, tot; //cnt：强连通分量的数量， ind：时间戳， tot：sta的top
int sd[maxn];//缩点点后在哪个点
int in[maxn];//入度
int dist[maxn];
vector<int> sdg[maxn];
int n,m;
void init()
{
    memset(ins, 0, sizeof(ins));
    memset(belong, 0, sizeof(belong));
    memset(dfn, 0, sizeof(dfn));
    cnt = ind = tot = 0;
}
//求强连通分量
void Tarjan(int u)
{
    low[u] = dfn[u] = ++ind;
    ins[u] =1;
    sta[++tot] = u;
    for(int i=0;i<g[u].size();i++)
    {
        int v = g[u][i];
        if(!dfn[v])
        {
            Tarjan(v);
            low[u] = min(low[u],low[v]);
        }
        else if(ins[v])
        {
            low[u] = min(low[u],low[v]);
        }
    }
    int p;
    if(low[u] == dfn[u])
    {
        ++cnt;
        int y;
        while(y=sta[tot--])
        {
            sd[y] = u;
            ins[y] = 0;
            if(u==y) break;
            val[u]+=val[y];
            //cout<<"asd"<<endl;
        }
//这行代码会加了两次
//        do
//        {
//            p = sta[tot--];
//            sd[p] =u;
//            val[u]+=val[p];
//            cout<<"asd"<<endl;
//            //belong[p] = cnt;
//            ins[p] = 0;
//        }while(p!=u);
    }

}
int tuopu()
{
    queue <int> q;
	//int tot=0;
	for (int i=1;i<=n;i++)
        if (sd[i]==i&&!in[i])
        {
            q.push(i);
            dist[i]=val[i];
            //cout<<i<<" "<<dist[i]<<endl;
        }

    while(!q.empty())
    {
        int k=q.front();q.pop();
        for(int i=0;i<sdg[k].size();i++)
        {
            int v = sdg[k][i];
            dist[v] = max(dist[v],dist[k]+val[v]);
            in[v]--;
            if(in[v]==0) q.push(v);
        }
    }
    int ans=0;
    for (int i=1;i<=n;i++)
        ans=max(ans,dist[i]);
    return ans;
}
/*
5 5
1 2 3 4 5
1 2
2 3
2 4
3 5
4 1

*/
int main()
{

    IO;
    cin>>n>>m;
    for (int i=1;i<=n;i++)
        cin>>val[i];
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
    }
    init();
    for (int i=1;i<=n;i++)
        if (!dfn[i]) Tarjan(i);
//    for(int i=1;i<=n;i++)
//        cout<<belong[i]<<" ";
//        for(int i=1;i<=n;i++)
//            cout<<sd[i]<<" ";
    //缩点，建图
    for(int i=1;i<=n;i++)
    for(int j=0;j<g[i].size();j++)
    {
        int x = sd[i],y=sd[g[i][j]];
        //cout<<x<<" "<<y<<endl;
        if(x!=y)
        {
            sdg[x].push_back(y);
            in[y]++;
        }
    }
    cout<<tuopu()<<endl;
    return 0;
}

sdg就是缩点后的图。

这题缩点后需要拓扑排序，稍详细的题解下篇博客再说。

然后给出一些缩点的练习题，也是洛谷的：

受欢迎的牛

消息扩散

间谍网络

下篇博客给出我的垃圾题解。

本博客参考的一些博客有：

http://elitedj.me/2019/10/01/Tarjan%E6%B1%82%E8%A7%A3%E5%BC%BA%E8%BF%9E%E9%80%9A%E5%88%86%E9%87%8F%E3%80%81%E5%89%B2%E7%82%B9%E3%80%81%E6%A1%A5/#more

https://blog.csdn.net/m0_38033475/article/details/80081253

https://www.cnblogs.com/stxy-ferryman/p/7779347.html

Tarjan求强连通分量，割点，桥，和缩点。

Tarjan

强连通分量

割点

桥

Tarjan缩点

继续阅读

Codeforces 1417 D. Make Them Equal(思维+构造)

查找算法之二分查找查找算法之二分查找

查找算法学习之二分查找（Python版本）——BinarySearch

CQ V1.0分词bates(基于双数组tire树)—应该是目前最快的中文分词算法

Command Network(POJ 3164)---定根最小树形图模板题题目描述输入格式输出格式输入样例输出样例分析源程序

开源低带宽语音编解码器

241 Different Ways to Add Parentheses（C代码版）

【趋高机器视觉】机器视觉技术原理解析及解决方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制规程及特点4． CSMA/CD协议5． CSMA/CD的优点6．结束语

极大似然法(ML)与最大期望法(EM)

C++ 第十五周报告1--《冒泡法排序》

笔试面试题目：滑动窗口(二)

数据结构与算法（27）——排序（二）

Dijkstra--简易版（最短路径）

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

hdu7108哈希