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哈希