1. 差分約束

1.1. 簡介

差分約束算法用于解決如下問題：給出若干形如 \(x_a-x_b\le c\) （均為整數，可以為負數）的不等式，求一組解 \(\{x_i\}\)，若不存在解則判斷無解。

考慮將原式變形，變為 \(x_a\le x_b+c\)。觀察到這與單源最短路里的三角形不等式 \(dis_a\le dis_b+w\) （\(w\) 為節點 \(a,b\) 之間的某邊邊權）相似。我們使 \(x_i\) 為從源點到節點 \(i\) 的最短路徑，對于不等式 \(x_a\le x_b+c\) 我們從節點 \(b\) 向節點 \(a\) 連一條邊權為 \(c\) 的有向邊。特殊地，我們建立一個源點 \(0\)，從源點向所有節點連一條邊權為 \(0\) 的有向邊，并以源點作為最短路起點。

我們一般采用 SPFA 進行最短路，若圖中存在負環，則差分約束系統無解。

特殊地，有些題也可轉化為最長路形式進行拓撲排序，因題而異。

1.2. 常見技巧

1.2.1. 常見變形

1.2.2. 簡單性質

顯著的，將我們得出的一組解 \(x_i\) 整體加減一個常量不影響正確性，因為都消掉了。

1.3. 例題

\(\color{limegreen}{P5960}\)

差分約束模板題。

#define LL long long

#define UN unsigned

#include<bits/stdc++.h>

using namespace std;

//--------------------//

const int N=1e5+2,M=1e5+2;

int n,m;

//----------//

//Edge

struct Edge

{

    int to,w,nex;

}edge[M];

int tot,head[N];

void add(int from,int to,int w)

{

    edge[++tot].nex=head[from];

    head[from]=tot;

    edge[tot].to=to;

    edge[tot].w=w;

    return;

}

//--------------------//

//SPFA

bool vq[N];

int v[N],dis[N];

queue<int>q;

void SPFA(int st)

{

    //printf("ST:%d\n",st);

    memset(v,0,sizeof(v));

    memset(vq,0,sizeof(vq));

    memset(dis,0x3f,sizeof(dis));

    dis[st]=0;

    vq[st]=true;

    q.push(st);

    while(!q.empty())

    {

        int now=q.front();

        //printf("now:%d\n",now);

        q.pop();

        vq[now]=false,v[now]++;

        if(v[now]>n)

            printf("NO"),exit(0);

        for(int to,w,i=head[now];i;i=edge[i].nex)

        {

            to=edge[i].to,w=edge[i].w;

            //printf("to:%d %d %d\n",to,dis[to],dis[now]+w);

            if(dis[now]+w<dis[to])

            {

                dis[to]=dis[now]+w;

                //printf("%d %d %d\n",dis[to],dis[now],w);

                if(!vq[to])

                    q.push(to),vq[to]=true;

            }

        }

    }

}

//-------------------//

int main()

{

    scanf("%d%d",&n,&m);

    for(int from,to,w,i=1;i<=m;i++)

    {

        scanf("%d%d%d",&to,&from,&w);

        add(from,to,w);

    }

    for(int i=1;i<=n;i++)

        add(n+1,i,0);

    SPFA(n+1);

    for(int i=1;i<=n;i++)

    {

        if(dis[i]==0x3f3f3f3f)

            dis[i]=0;

        printf("%d ",dis[i]);

    }

    return 0;

}

\(\color{royalblue}{P3275}\)

將不等式列出之后注意轉化、建邊細節，這道題用 SPFA 會被卡，需要轉化為最長路用拓撲排序求解。

\(\color{blueviolet}{P3530}\)

非常好題目。

一個強連通分量答案固定，多個之間互不影響，考慮一個強連通分量貢獻。

考慮此題一個特點，兩個點點權相差不超過 \(1\)，也就是說強連通分量中點權極值 \(v_x\) 到 \(v_y\) 中每個值都能去到，自然而然答案就是最長路加一，即 \(\min\{dis(i,j) + 1\}\)（\(i,j\) 都為其中的點），Floyd 求解即可。

2. 有向圖連通性：強連通分量

2.1. 強連通定義

• 強連通：對于有向圖兩點 \(x,y\)，若他們互相可達，則稱 \(x,y\) 強連通，這種性質為強連通性。
• 強連通圖：滿足任意兩點強連通的有向圖稱為強連通圖。
• 強連通分量：有向圖的極大強連通子圖稱為強連通分量（SCC）。

顯著的，強連通性具有傳遞性，并且強連通的兩者等價。當在做某些只關心連通性的問題時，一個強連通分量內所有節點等價，便于做題。

2.2. 有向圖 DFS 樹

遍歷每一個節點，若此節點未被訪問，則以此節點為根進行 DFS，對于整個圖搜索完后可以得到一個有向圖 DFS 森林。

對于一棵 DFS 樹，主要有以下 \(4\) 種邊：

1. 樹邊：每次從父節點向子節點進行 DFS 的邊。
2. 返祖邊：DFS 時訪問到當前節點祖先的邊。
3. 橫叉邊：DFS 時訪問到非當前節點子樹內且不是當前節點祖先的點的邊。
4. 前向邊：DFS 時訪問到當前節點子樹內已經訪問過的邊。

對于兩點 \(x,y\)，設 \(d_{x,y}=lca(x,y)\)，\(fa_i\) 為節點 \(i\) 的父節點，\(T_i\) 為節點 \(i\) 的子樹，\(dfn_i\) 為節點 \(i\) 的時間戳。

我們不難發現如下性質：

• 對于返祖邊 \(x\to y\)，它使得 \(x\) 到 \(y\) 的 DFS 樹上路徑上的節點強連通。
• 對于橫叉邊 \(x\to y\)，有 \(dfn_y<dfn_x\)。
• 對于前向邊 \(x\to y\)，刪去它并不會影響連通性。

橫叉邊、前向邊均可減小時間戳，而樹邊和前向邊會增大時間戳。由于刪去前向邊并不會影響連通性，在接下來的證明中，我們忽略前向邊的影響。

為了研究橫叉邊對連通性的影響，我們假設存在節點 \(x,y\) 使得 \(dfn_y<dfn_x\)，并且從節點 \(y\) 可達節點 \(x\)。考慮到 \(dfn_y<dfn_x\)，而且我們的圖中只有樹邊可以增大時間戳（前向邊已經被忽略），所以 \(y\) 到 \(x\) 的路徑上一定存在至少一條樹邊，且一定是通過某一條樹邊從節點 \(fa_x\) 達到 \(x\)。

所以若 \(y\) 可達 \(x\) 并且 \(dfn_y<dfn_x\)，那么 \(y\) 可達 \(fa_x\)，那么 \(y\) 一定可達 \(d_{x,y}\)。

相反地，若 \(y\) 可達 \(d_{x,y}\)，顯然 \(y\) 可達 \(d_{x,y}\)。（別忘了前提 \(dfn_y<dfn_x\)。）

可推出結論：

• 若 \(dfn_y<dfn_x\)，\(y\) 可達 \(x\) 當且僅當 \(y\) 可達 \(d_{x,y}\)。

重新考慮橫叉邊對連通性的影響，設橫叉邊 \(x\to y\)，利用上述結論，不難發現當且僅當 \(y\) 可達 \(d_{x,y}\) 時，\(x,y\) 強連通。

進一步推出：

• 若 \(x,y\) 強連通，則 \(x,y\) 路徑上的所有點強連通。

2.3. Tarjan 求有向圖 SCC

對于每一個 SCC，定義它在 DFS 樹上的最淺的那個節點為其“關鍵點”，我們嘗試在一個關鍵點出求出它所對應的 SCC。顯著的，一個關鍵點有且只有一個對應的 SCC。

對于一個點 \(x\)，若它不是關鍵點，一定有 \(y\in T_x\) 使得有邊 \(y\to z\)，保證 \(dfn_z<dfn_x\)（這條邊是返祖邊或者橫叉邊）。

我們定義 \(low_x\) 為以下節點的 \(dfn\) 最小值：

• \(T_x\) 中的節點。
• 一條返祖邊 \(y\to z,y\in T_x\)，其指向的節點 \(z\)。
• 一條橫叉邊 \(y\to z,y\in T_x\)，若 \(z\) 可達 \(d_{y,z}\)，則包括節點 \(z\)。

若 \(x\) 為關鍵點，則一定有 \(low_x=x\)（我們把 \(low_x\) 初始化為 \(x\)）。比較顯著的特性，考慮分類討論每種邊的情況即可，這里省略證明。

我們已知如何尋找關鍵點，現在考慮求強連通分量。

考慮強連通分量的性質，每個 DFS 樹中，強連通分量都是弱連通的（顯著）。

根據此性質我們每次找到深度最大的強連通分量，將它與它子樹內未被刪除的點作為一個強連通分量，然后再刪除整個強連通分量。

我們可以用棧維護深搜過的節點，一旦找到整個強連通分量就將其彈出（彈到關鍵點彈出為止，關鍵點是深度最小的），使彈出的所有點成為一個 SCC。

現在唯一的問題就是如何求解 \(low\)，在回溯時用搜過的直系節點的 \(low,dfn\) 更新當前節點的 \(low\)，仍然考慮分類討論邊的種類。

對于現在搜索的到的節點 \(x\)，存在一條邊 \(x\to y\)。

• 若其為樹邊，\(low_x\leftarrow\min\{low_x,low_y\}\)。
• 若其為返祖邊，\(low_x\leftarrow\min\{low_x,dfn_y\}\)。
• 若其為橫叉邊，需要判斷 \(y\) 是否與 \(x\) 強連通，即判斷 \(y\) 是否在棧中，若強連通，\(low_x\leftarrow\min\{low_x,dfn_y\}\)。
• 若其為前向邊，\(low_x\leftarrow\min\{low_x,dfn_y\}\)，這并不會改變 \(low_x\) 的值，因為一定有 \(dfn_y>low_x\)。

對于返祖邊 \(x\to y\) 來說，\(y\) 一定未出棧，所以在實現時可以采用與橫叉邊相同的判斷方式；對于前向邊，如何處理都無所謂。

綜上，我們得到了求 \(low\) 的方式。

• \(low_x\) 初始值設為 \(dfn_x\)。
• 若當前邊 \(x\to y\) 為樹邊，\(low_x\leftarrow\min\{low_x,low_y\}\)。
• 若當前邊 \(x\to y\) 為非樹邊，并且 \(y\) 未出棧，\(low_x\leftarrow\min\{low_x,dfn_y\}\)。

2.4. 常用技巧

2.4.1. 縮點

在一定條件下，對于只關心連通性的問題時，一個 SCC 內所有節點等價，因此我們可以將一個 SCC 看做一個點，建出一張新圖（一定是一張 DAG），進一步計算。

2.4.2. 優化拓撲排序

對于兩個 SCC \(S_1,S_2\)，若 \(S_1\) 可達 \(S_2\)，則 \(S_1\) 比 \(S_2\) 后出棧。我們按照出棧順序依次為 SCC 編號，便可以得到 SCC 的拓撲序，所以倒序遍歷 SCC，相當于拓撲排序遍歷縮點后 DAG，省去了拓撲排序。

2.5. 例題

\(\color{limegreen}{P3387}\)

縮點模板，把 SCC 縮起來后在新圖（DAG）上 DP 即可。

\(\color{limegreen}{B3609}\)

強連通分量模板。

\(\color{royalblue}{P3627}\)

簡單題，跟板子沒啥區別，縮點后 DAG 上 DP。

3. 無向圖連通性：雙連通分量

3.1. 基本定義

• 割點：無向圖中，刪去此節點使得連通分量數量增加，則稱此節點為割點。
• 割邊：無向圖中，刪去此邊使得連通分量數量增加，則稱此節點為割邊。

連通分量也就是熟悉的連通塊。

分量（極大子圖）：在滿足一定條件下，當且僅當 \(\forall G''\) 滿足條件使得 \(G'\subsetneq G''\subseteq G\)，則稱 \(G'\) 為滿足此條件的分量。

• 點雙連通分量：不存在割點的分量。
• 邊雙連通分量：不存在割邊的分量。

特殊地，孤立點不是割點，是點雙連通圖，是邊雙連通分量；孤立邊的端點不是割點，孤立邊是割邊，是點雙連通圖，不是邊雙連通圖。

• 點雙連通：若 \(x,y\) 處于同一個點雙，則稱 \(x,y\) 點雙連通。
• 邊雙連通：若 \(x,y\) 處于同一個邊雙，則稱 \(x,y\) 邊雙連通。

3.2. 基本性質

3.2.1. 邊雙

1. 考慮一條割邊 \((u, v)\)，以及其兩側任意兩點 \(x, y\)，有任意 \(x, y\) 之間路徑都包含割邊 \((u, v)\)。

2. 與強連通分量類似，考慮將一個邊雙中的所有點縮成一個新點，并建出新圖，那么此圖一定是一棵樹，所有樹邊都是割邊，在此性質基礎上對于特定題目可以轉換為樹上問題。

3. 邊雙連通具有傳遞性，若 \(a, b\) 邊雙連通，且 \(b, c\) 邊雙連通，則 \(a, c\) 邊雙連通。

3.2.2. 點雙

1. 考慮一個割點 \(u\)，以及其兩側任意兩點 \(x, y\)，有任意 \(x, y\) 之間路徑都包含割點 \(u\)。
2. 點雙交點一定是割點，割點一定是點雙的交點。
3. 點雙連通不具有傳遞性，因為點雙可以交于割點。
4. 一條邊恰好屬于一個點雙。

3.3. Tarjan 求割點

將根節點與非根節點分開考慮，時刻記住是在無向圖 DFS 樹上進行處理，基于無向圖 DFS 樹的性質，會對理解有很大幫助。

非根節點：

若非根節點 \(x\) 是割點，則其子樹內存在點不通過 \(x\) 能到達的所有點均在 \(x\) 子樹內，若其不是，那么一定其子樹內任意節點可以通過非樹邊到達某個已經被訪問過的點 \(y\)，一定有 \(dfn_y < dfn_x\)，所以定義 \(low_i\) 表示 \(i\) 子樹內的點通過非樹邊能達到的 \(dfn\) 值最小的一點。\(x\) 是割點當且僅當任意一個子節點 \(u\) 使得 \(low_u < dfn_x\)，等價于存在一個子節點 \(u\) 使得 \(low_u \ge dfn_x\)。

根節點：

因為是無向圖 DFS 樹，若根節點 \(x\) 有大于一個子節點，則刪去 \(x\) 后各個子樹不連通，\(x\) 為割點。

3.4. Tarjan 求割邊

仍然考慮在無向圖 DFS 樹上處理，因為刪掉非樹邊不影響連通性，所以割邊一定是樹邊。

設邊 \(e = (u, v)\) 為樹邊，并且 \(u\) 為 \(v\) 父節點，\(e\) 為割邊當且僅當 \(low_v > dfn_u\)，這與求割點是類似的。

在求割邊時應注意當重邊的影響，所以在判斷非樹邊的時候應以邊的編號為標準，而不是以端點是否是父節點為標準。

3.5. 例題

\(\color{limegreen}{P8436}\)

邊雙模板。

\(\color{limegreen}{P8435}\)

點雙模板。

\(\color{limegreen}{P3388}\)

割點模板。

\(\color{royalblue}{P2860}\)

首先考慮進行邊雙縮點，于是得到一棵樹，題意轉化為給定一棵樹，問添加多少邊使得整張圖變為一個點雙。

易證添加的邊連葉子是最優策略，考慮這樣縮成點雙影響到的點是最多的。

先將葉子任意兩兩匹配，剩余一個的處理方式是簡單的，考慮是否存在無解。

對于一條邊 \((u, v)\)，設其兩側子圖分別為 \(U, V\)，顯然 \(U, V\) 中各有偶數個葉子，否則 \((u, v)\) 一定會被覆蓋。

調整方式即拆開一對連在 \(U\) 或 \(V\) 內的匹配，令其跨 \((u, v)\) 相連，這樣顯然不劣，故一定有解，答案為縮點后葉子個數除以二上取整。

\(\color{royalblue}{P3469}\)

非割點的貢獻是簡單的，考慮割點答案構成。

去掉割點后在子樹內會形成若干連通塊，對于一個大小為 \(x\) 的連通塊貢獻為 \(x (n - x)\)，特別的還要考慮不在割點子樹的那個連通塊，實現是簡單的。

總結

以上是生活随笔為你收集整理的「Note」图论方向 - 图论基础的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。