国产无码综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

第三章圖論 No.9有向圖的強(qiáng)連通與半連通分量

2年前作者：.SacaJawea分類：Toy博客閱讀(17)違法舉報(bào)

這篇具有很好參考價(jià)值的文章主要介紹了第三章圖論 No.9有向圖的強(qiáng)連通與半連通分量。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問(wèn)。

定義

連通分量是無(wú)向圖的概念，yxc說(shuō)錯(cuò)了，不要被誤導(dǎo)
強(qiáng)連通分量：在一個(gè)有向圖中，對(duì)于分量中的任意兩點(diǎn)u，v，一定能從u走到v，且能從v走到u。強(qiáng)連通分量是一些點(diǎn)的集合，若加入其他點(diǎn)，強(qiáng)連通分量中的任意兩點(diǎn)就不能互相遞達(dá)
半連通分量：在一個(gè)有向圖中，對(duì)于分量中的任意兩點(diǎn)u，v，一定存在從u走到v或者從v的路徑

應(yīng)用：通過(guò)縮點(diǎn)（將所有強(qiáng)連通分量縮成一個(gè)點(diǎn)）的方式，那么一個(gè)有向圖就轉(zhuǎn)換成了一個(gè)有向無(wú)環(huán)圖DAG（拓?fù)鋱D）
對(duì)于拓?fù)鋱D，可以直接用bfs求最短路問(wèn)題

第三章圖論 No.9有向圖的強(qiáng)連通與半連通分量,AcWing算法提高課課程記錄,圖論,深度優(yōu)先,算法

樹(shù)枝邊（x和y直接相連）
前向邊（y是x的祖先節(jié)點(diǎn)）
后向邊（前向邊的反）
橫叉邊（指向已經(jīng)遍歷過(guò)的其他分支上的點(diǎn)）

樹(shù)枝邊是一種特殊的前向邊
第三章圖論 No.9有向圖的強(qiáng)連通與半連通分量,AcWing算法提高課課程記錄,圖論,深度優(yōu)先,算法

強(qiáng)連通分量簡(jiǎn)稱scc，如何判斷當(dāng)前點(diǎn)是否在scc中？

存在一條后向邊，指向祖先節(jié)點(diǎn)
先走橫叉邊，橫叉邊連接了后向邊

無(wú)論如何，其一定能走到已經(jīng)遍歷過(guò)的祖先節(jié)點(diǎn)上
點(diǎn)可能存在自環(huán)，也是強(qiáng)連通分量（書上說(shuō)自環(huán)不是強(qiáng)連通分量，但是為了算法的實(shí)現(xiàn)，將自環(huán)認(rèn)為是強(qiáng)連通分量）

Tarjan求SCC

給定時(shí)間戳的概念，從小到大的時(shí)間為dfs的順序
那樹(shù)枝邊的y一定比x大1，前向邊的y一定大于等于x+1
后向邊的y一定小于x，橫叉邊也是
對(duì)每個(gè)點(diǎn)定義兩個(gè)時(shí)間戳：
dfs[u]表示遍歷到u的時(shí)間
low[u]表示從u開(kāi)始走，能遍歷到的最小時(shí)間戳
若u是強(qiáng)連通分量的最高點(diǎn)，那么dfn[u] == low[u]，即該點(diǎn)無(wú)法再往上走到其他點(diǎn)

板子中使用了兩個(gè)棧，一個(gè)是系統(tǒng)函數(shù)棧，用來(lái)深搜。一個(gè)是自定義的棧，保存當(dāng)前正在遍歷的強(qiáng)連通分量中的所有點(diǎn)

板子 $O (n + m)$ ：

void tarjan(int x)
{
	dfn[x] = low[x] = ++ tp;
	stk[ ++ tt] = x, st[x] = true;
	for (int i = h[x]; i != -1; i = ne[i])
	{
		int y = e[i];
		if (!dfn[y])
		{
			tarjan(y);
			low[x] = min(low[x], low[y]);
		}
		else if (st[y]) low[x] = min(low[x], dfn[y]);
	}
	if (low[x] = dfn[x])
	{
		int y;
		++ cnt;
		do{
			y = stk[tt -- ]， st[y] =false;
			id[y] = cnt;
		} while (y != x)
	}
}

縮點(diǎn)：遍歷所有點(diǎn)，再遍歷其所有鄰點(diǎn)，若兩點(diǎn)不在同一強(qiáng)連通分量中，將這兩點(diǎn)之間添加一條邊
強(qiáng)連通分量編號(hào)遞減的順序一定是拓?fù)湫?，求拓?fù)湫蛞话闶褂胋fs，除此之外還能使用dfs
遍歷所有點(diǎn)，從入邊為0的點(diǎn)開(kāi)始，dfs其所有鄰點(diǎn)，完成后將該點(diǎn)的編號(hào)加入序列中，序列的逆序就是拓?fù)湫?。因?yàn)槊看芜M(jìn)入序列的點(diǎn)一定無(wú)后繼（或者后繼節(jié)點(diǎn)已經(jīng)進(jìn)入序列的點(diǎn)）
不過(guò)，若圖中存在多個(gè)入邊為0的點(diǎn)，選擇其一進(jìn)行dfs即可，后續(xù)要在拓?fù)湫蜷_(kāi)頭加上這幾個(gè)入邊為0的點(diǎn)

1174. 受歡迎的牛

1174. 受歡迎的牛 - AcWing題庫(kù)
第三章圖論 No.9有向圖的強(qiáng)連通與半連通分量,AcWing算法提高課課程記錄,圖論,深度優(yōu)先,算法

反向建圖，遍歷所有點(diǎn)，用bfs判斷當(dāng)前點(diǎn)是否能遞達(dá)其他所有點(diǎn)，時(shí)間復(fù)雜度為 $O(n^2)$
如果不反向建圖，就要判斷圖中有幾個(gè)出邊為0的點(diǎn)，若有1個(gè)，那么這個(gè)點(diǎn)就是最受歡迎的，若有>1個(gè)，那么不存在最受歡迎的點(diǎn)，若有0個(gè)，說(shuō)明圖中一定存在環(huán)（強(qiáng)連通分量），環(huán)中的節(jié)點(diǎn)數(shù)量為受歡迎的點(diǎn)的數(shù)量

將所有的強(qiáng)連通分量（環(huán)）縮成一個(gè)點(diǎn)，此時(shí)圖中出邊為0的點(diǎn)的數(shù)量不可能為0
只要判斷數(shù)量是否為1即可
若出邊為的點(diǎn)的數(shù)量為1，說(shuō)明該強(qiáng)連通分量中的所有點(diǎn)都是受歡迎的，統(tǒng)計(jì)環(huán)中節(jié)點(diǎn)的數(shù)量即可

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e4 + 10, M = 5e4 + 10;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], tp, cnt;
int stk[N], tt; bool st[N];
int dout[N], id[N], sz[N]; // 每個(gè)強(qiáng)連通分量中的節(jié)點(diǎn)數(shù)量
int n, m;

void add(int x, int y)
{
    e[idx] = y, ne[idx] = h[x], h[x] = idx ++ ;
}

void tarjan(int x)
{
    stk[ ++ tt] = x, st[x] = true;
    dfn[x] = low[x] = ++ tp;
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int y = e[i];
        if (!dfn[y])
        {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        }
        else if (st[y]) low[x] = min(low[x], dfn[y]);
    }
    if (dfn[x] == low[x])
    {
        int y;
        cnt ++ ;
        do {
            y = stk[tt -- ], st[y] = false;
            id[y] = cnt;
            sz[cnt] ++ ;
        } while (y != x);
    }
}

int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d%d", &n, &m);
    int x, y;
    for (int i = 0; i < m; ++ i )
    {
        scanf("%d%d", &x, &y);
        add(x, y);
    }
    
    for (int i = 1; i <= n; ++ i )
        if (!dfn[i]) tarjan(i);
        
    for (int x = 1; x <= n; ++ x ) 
        for (int i = h[x]; i != -1; i = ne[i])
        {
            int y = e[i];
            int a = id[x], b = id[y];  
            if (a != b) dout[a] ++ ;
        }
        
    int ans = 0, t = 0;
    for (int i = 1; i <= cnt; ++ i )
        if (!dout[i])
        {
            t ++ ;
            ans = sz[i];
            if (t > 1)
            {
                ans = 0;
                break;
            }
        }
        
    printf("%d\n", ans);
    return 0;
}

debug到死的一道題：
首先tp要前置++，雖然tp是時(shí)間戳的概念，但是在數(shù)組中作為下標(biāo)還對(duì)應(yīng)著節(jié)點(diǎn)編號(hào)
最后檢查dout數(shù)組中，循環(huán)從1到cnt，不是從1到n，也不是從1到cnt - 1，因?yàn)閏nt不是后置++，而是++完再使用
else if (st[y]) low[x] = min(low[x], dfn[y]);寫歪了，寫成
else if (st[y]) low[x] = min(low[x], dfn[x]);

367. 學(xué)校網(wǎng)絡(luò)

367. 學(xué)校網(wǎng)絡(luò) - AcWing題庫(kù)
第三章圖論 No.9有向圖的強(qiáng)連通與半連通分量,AcWing算法提高課課程記錄,圖論,深度優(yōu)先,算法

將所有強(qiáng)連通分量縮點(diǎn)后，圖中入度為0的點(diǎn)為第一問(wèn)的答案
第二問(wèn)是：任何一個(gè)有向無(wú)環(huán)圖，需要加幾條邊才能使之成為一個(gè)強(qiáng)連通分量
結(jié)論：假設(shè)有向無(wú)環(huán)圖有P個(gè)入度為0的點(diǎn)，Q個(gè)出度為0的點(diǎn)，需要加max(P, Q)個(gè)點(diǎn)
第三章圖論 No.9有向圖的強(qiáng)連通與半連通分量,AcWing算法提高課課程記錄,圖論,深度優(yōu)先,算法

設(shè)起點(diǎn)的集合為P，終點(diǎn)的集合為Q
假設(shè) $∣ P ∣ <= ∣ Q ∣$ ，若 $∣ P ∣ > ∣ Q ∣$ ，建個(gè)反圖即可
考慮兩種情況， $∣ P ∣ = 1$ ，此時(shí)將所有的終點(diǎn)向起點(diǎn)連一條邊，即 $Q$ 條邊。此時(shí)從起點(diǎn)一定能走到所有點(diǎn)，從中間點(diǎn)一定能走到終點(diǎn)，而終點(diǎn)一定能走到起點(diǎn)，從而走完所有點(diǎn)。所以此時(shí)圖中任意一點(diǎn)能走完圖中所有點(diǎn)
$∣ P ∣ > 1$ 時(shí)，在終點(diǎn)與起點(diǎn)之間連一條邊（盡可能與無(wú)法到達(dá)該終點(diǎn)的起點(diǎn)連線），直到起點(diǎn)的數(shù)量為1（每次連完邊后，起點(diǎn)數(shù)量與終點(diǎn)數(shù)量都減一），此時(shí)的情況為 $∣ P ∣ = 1$ 的情況 $∣ Q ∣ ? (∣ P ∣ ? 1)$ 條邊即可，由于已經(jīng)連了 $∣ P ∣ ? 1$ 條邊，所以總共需要連的邊數(shù)為 $∣ Q ∣$

#include <iostream>
#include <cstring>
using namespace std;

const int N = 110, M = N * N;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], tp, cnt;
int id[N], stk[N], tt;
bool st[N];
int din[N], dout[N];
int n, t;

void add(int x, int y)
{
    e[idx] = y, ne[idx] = h[x], h[x] = idx ++ ;
}

void tarjan(int x)
{
    st[x] = true, stk[ ++ tt] = x;
    dfn[x] = low[x] = ++ tp;
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int y = e[i];
        if (!dfn[y])
        {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        }
        else if (st[y]) low[x] = min(low[x], dfn[y]);
    }
    if (dfn[x] == low[x])
    {
        int y;
        cnt ++ ;
        do {
            y = stk[tt -- ], st[y] = false;
            id[y] = cnt;
        } while (x != y);
    }
}

int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d", &n);
    int y;
    for (int x = 1; x <= n; ++ x )
        while (scanf("%d", &y), y)
            add(x, y);
            
    for (int i = 1; i <= n; ++ i )
        if (!dfn[i])
            tarjan(i);

    
    int u = 0;
    for (int x = 1; x <= n; ++ x)
        for (int i = h[x]; i != -1; i = ne[i])
        {
            int y = e[i];
            int a = id[x], b = id[y];
            if (a != b) din[b] ++, dout[a] ++ ;
        }
        
    int in = 0, out = 0;
    for (int i = 1; i <= cnt; ++ i )
    {
        if (!din[i]) in ++ ;
        if (!dout[i]) out ++ ;
    }
    if (cnt == 1) printf("%d\n%d\n", in, 0);
    else printf("%d\n%d\n", in, max(in, out));
    
    return 0;
}

debug：dfs的次數(shù)與縮點(diǎn)后入度為0的點(diǎn)的數(shù)量不一定相同
縮點(diǎn)后的圖中可能存在入度和出度都為0的點(diǎn)，所以判斷要用兩個(gè)if
最后要注意，縮點(diǎn)后的圖只有一個(gè)連通分量時(shí)，需要特判輸出

1175. 最大半連通子圖

1175. 最大半連通子圖 - AcWing題庫(kù)
第三章圖論 No.9有向圖的強(qiáng)連通與半連通分量,AcWing算法提高課課程記錄,圖論,深度優(yōu)先,算法

第三章圖論 No.9有向圖的強(qiáng)連通與半連通分量,AcWing算法提高課課程記錄,圖論,深度優(yōu)先,算法

首先，強(qiáng)連通分量一定是半連通分量，所以可以先找出圖中所有強(qiáng)連通分量
用tarjan將圖縮點(diǎn)，得到由強(qiáng)連通分量組成的有向無(wú)環(huán)圖，此時(shí)再找出極大半連通分量（有向圖中點(diǎn)最多的一條路徑），可以按照拓?fù)湫蜻f推，找一條最長(zhǎng)路
由于每個(gè)點(diǎn)都是強(qiáng)連通分量，計(jì)算最長(zhǎng)路的節(jié)點(diǎn)數(shù)量時(shí)，需要累加所有“節(jié)點(diǎn)”（強(qiáng)連通分量）中的節(jié)點(diǎn)數(shù)量，只能在按照拓?fù)湫蜻f推最長(zhǎng)路時(shí)，將邊權(quán)設(shè)置為分量中的點(diǎn)數(shù)

若縮點(diǎn)后的兩點(diǎn)之間存在多條邊，因?yàn)閷?dǎo)出子圖一定會(huì)將和點(diǎn)有關(guān)的所有邊選擇，所以邊數(shù)不同不能算不同的半連通子圖，半連通分量中不存在只選擇兩點(diǎn)之間一部分邊的情況，因此點(diǎn)數(shù)不同才算不同的半連通子圖
由于我們找最長(zhǎng)路時(shí)，需要使用邊的權(quán)重，重邊將影響最長(zhǎng)路的求解，所以在建立縮點(diǎn)后的圖時(shí)要注意給邊判重
邊的權(quán)重是分量中點(diǎn)的數(shù)量，與這些兩點(diǎn)之間的重邊沒(méi)有關(guān)系，因此只需要在兩點(diǎn)之間建立一條邊

縮點(diǎn)建圖完成后，就是遞推求最長(zhǎng)路。由于縮點(diǎn)的遞歸順序是拓?fù)湫虻哪嫘颍晕覀兡嬷闅v縮點(diǎn)的順序，按照拓?fù)湫蜻f推求最長(zhǎng)路即可。注意不僅要記錄最長(zhǎng)路的權(quán)值還要記錄最長(zhǎng)路的數(shù)量，分別對(duì)應(yīng)最大半連通子圖中點(diǎn)的數(shù)量以及最大半連通子圖的數(shù)量

#include <iostream>
#include <cstring>
#include <unordered_set>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10, M = 2e6 + 10;
int h[N], hs[N], e[M], ne[M], idx;
int dfn[N], low[N], cnt, tp;
int stk[N], tt; bool st[N];
unordered_set<LL> s;
int sz[N], id[N];
int f[N], g[N];
int n, m, X;

void add(int h[], int x, int y)
{
    e[idx] = y, ne[idx] = h[x], h[x] = idx ++ ;
}

void tarjan(int x)
{
    dfn[x] = low[x] = ++ tp;
    st[x] = true, stk[ ++ tt] = x;
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int y = e[i];
        if (!dfn[y])
        {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        }
        else if (st[y]) low[x] = min(low[x], dfn[y]);
    }
    if (dfn[x] == low[x])
    {
        int y;
        cnt ++ ;
        do {
            y = stk[tt -- ], st[y] = false;
            id[y] = cnt;
            sz[cnt] ++ ;
        } while (x != y);
    }
}

int main()
{
    memset(h, -1, sizeof(h));
    memset(hs, -1, sizeof(hs));
    scanf("%d%d%d", &n, &m, &X);
    int x, y;
    for (int i = 0; i < m; ++ i )
    {
        scanf("%d%d", &x, &y);
        add(h, x, y);
    }
    
    for (int i = 1; i <= n; ++ i )
        if (!dfn[i]) tarjan(i);
        
    for (int x = 1; x <= n; ++ x )
        for (int i = h[x]; i != -1; i = ne[i])
        {
            int y = e[i];
            int a = id[x], b = id[y];
            if (a != b)
            {
                LL t = a * 100000ll + b;
                if (!s.count(t)) 
                {
                    add(hs, a, b);
                    s.insert(t);
                }
            }
        }
    for (int x = cnt; x; -- x )
    {
        if (!f[x]) f[x] = sz[x], g[x] = 1;
        for (int i = hs[x]; i != -1; i = ne[i])
        {
            int y = e[i];
            if (f[y] < f[x] + sz[y])
            {
                f[y] = f[x] + sz[y];
                g[y] = g[x];
            }
            else if (f[y] == f[x] + sz[y]) 
                g[y] = (g[x] + g[y]) % X;
        }
    }
    
    int maxf = 0, sum = 0;
    for (int i = 1; i <= cnt; ++ i )
    {
        if (f[i] > maxf)
        {
            maxf = f[i];
            sum = g[i];
        }
        else if (f[i] == maxf) sum = (sum + g[i]) % X;
    }
    printf("%d\n%d\n", maxf, sum);
    return 0;
}

debug：unordered_set比set快很多，當(dāng)然，也比unordered_map快
最后的最長(zhǎng)路遞推沒(méi)有按照拓?fù)湫颍╟nt的逆序）
沒(méi)有去重，遞推時(shí)要遍歷縮點(diǎn)后的圖
遞推時(shí)：

if (f[y] < f[x] + sz[y])
{
	f[y] = f[x] + sz[y];
	g[y] = g[x];
}

寫成了g[y] = f[x]，手滑了，但是這種錯(cuò)誤真的超難debug

368. 銀河

368. 銀河 - AcWing題庫(kù)
第三章圖論 No.9有向圖的強(qiáng)連通與半連通分量,AcWing算法提高課課程記錄,圖論,深度優(yōu)先,算法

很直接的不等式關(guān)系，一眼差分約束，首先轉(zhuǎn)換不等式關(guān)系，由于題目要求最小值，所以要用最短路，所有不等式要轉(zhuǎn)換成>=的形式

A >= B, B >= A
B >= A + 1
A >= B
A >= B + 1
B >= A

并且題目提供了一個(gè)邊界， $x_i >= 1$ ，轉(zhuǎn)換成 $x_i >= x_0 + 1$
那么 $x_0$ 為虛擬源點(diǎn)，與所有點(diǎn)有一條邊權(quán)為1的邊，從 $x_0$ 開(kāi)始遍歷，一定能遍歷所有的點(diǎn)，也一定能遍歷所有的邊
所以從 $x_0$ 為源點(diǎn)，用spfa求最長(zhǎng)路，并且判斷負(fù)環(huán)（無(wú)解）即可

這題和1169. 糖果一樣，解法一樣，數(shù)據(jù)一樣，但是時(shí)間限制卡的很死。用sfpa求最長(zhǎng)路與正環(huán)會(huì)超時(shí)
正解是：用線性時(shí)間復(fù)雜度的tarjan求強(qiáng)連通分量，判斷每個(gè)強(qiáng)連通分量是否是正環(huán)。由于圖中只有權(quán)值為0和1的邊，環(huán)中權(quán)值為0是個(gè)零環(huán)，只要有一條邊的權(quán)值為1，那么該強(qiáng)連通分量就是正環(huán)，返回?zé)o解
接著按照拓?fù)湫蚯笞铋L(zhǎng)路即可

#include <iostream>
#include <cstring>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10, M = 4e5 + 10;
int h[N], hs[N], e[M], ne[M], w[M], idx;
int dfn[N], low[N], cnt, tp;
int stk[N], tt; bool st[N];
int id[N], dis[N], sz[N];
int n, m;

void add(int h[], int x, int y, int d)
{
    e[idx] = y, ne[idx] = h[x], w[idx] = d, h[x] = idx ++ ;
}

void tarjan(int x)
{
    dfn[x] = low[x] = ++ tp;
    st[x] = true, stk[ ++ tt] = x;
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int y = e[i];
        if (!dfn[y])
        {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        }
        else if (st[y]) low[x] = min(low[x], dfn[y]);
    }
    if (dfn[x] == low[x]) 
    {
        int y;
        ++ cnt;
        do {
            y = stk[tt -- ], st[y] = false;
            id[y] = cnt;
            sz[cnt] ++ ;
        } while (x != y);
    }
}

int main()
{
    memset(h, -1, sizeof(h));
    memset(hs, -1, sizeof(hs));
    scanf("%d%d", &n, &m);
    int t, x, y;
    for (int i = 0; i < m; ++ i )
    {
        scanf("%d%d%d", &t, &x, &y);
        if (t == 1) add(h, x, y, 0), add(h, y, x, 0);
        else if (t == 2) add(h, x, y, 1);
        else if (t == 3) add(h, y, x, 0);
        else if (t == 4) add(h, y, x, 1);
        else add(h, x, y, 0);
    }
    for (int i = 1; i <= n; ++ i ) add(h, 0, i, 1);
    for (int i = 0; i <= n; ++ i ) 
        if (!dfn[i]) tarjan(i);

    for (int x = 0; x <= n; ++ x )
        for (int i = h[x]; i != -1; i = ne[i])
        {
            int y= e[i];
            int a = id[x], b = id[y];
            if (a == b && w[i] == 1)
            {
                puts("-1");
                return 0;
            }
            else if (a != b) add(hs, a, b, w[i]);
        }
        
    for (int x = cnt; x; -- x )
    {
        for (int i = hs[x]; i != -1; i = ne[i] )
        {
            int y = e[i];
            dis[y] = max(dis[y], dis[x] + w[i]);
        }
    }
    LL sum = 0;
    for (int i = 1; i <= cnt; ++ i ) sum += (LL)sz[i] * dis[i];
    printf("%lld\n", sum);
    
    return 0;
}

debug：遞推時(shí)又是沒(méi)有遍歷hs，縮點(diǎn)后的圖
虛擬源點(diǎn)的邊沒(méi)有提前建，之前做sfpa時(shí)習(xí)慣在spfa里直接將所有邊入隊(duì)了
同時(shí)，tarjan需要遍歷的點(diǎn)為0_{n之間的所有點(diǎn)，不是1}n
最后計(jì)算總和時(shí)，連通分量乘以距離才是正解文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-639174.html

到了這里，關(guān)于第三章圖論 No.9有向圖的強(qiáng)連通與半連通分量的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來(lái)自互聯(lián)網(wǎng)用戶投稿，該文觀點(diǎn)僅代表作者本人，不代表本站立場(chǎng)。本站僅提供信息存儲(chǔ)空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請(qǐng)注明出處：如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實(shí)不符，請(qǐng)點(diǎn)擊違法舉報(bào)進(jìn)行投訴反饋，一經(jīng)查實(shí)，立即刪除！

分享到：

領(lǐng)支付寶紅包贊助服務(wù)器費(fèi)用

Matlab論文插圖繪制模板第90期—帶權(quán)重的有向圖/圖論圖/網(wǎng)絡(luò)圖
在之前的文章中，分享了Matlab 有向圖的繪制模板：進(jìn)一步，如果我們想標(biāo)注有向圖的每條邊的權(quán)重，或者直接用線條的粗細(xì)來(lái)表示權(quán)重，該怎么操作呢？先來(lái)看一下成品效果：特別提示：本期內(nèi)容『數(shù)據(jù)+代碼』已上傳資源群中，加群的朋友請(qǐng)自行下載。有需要的朋友可
2024年02月16日
瀏覽(29)
第三章圖論 No.13拓?fù)渑判?/a>
拓?fù)湫蚝虳AG有向無(wú)環(huán)圖聯(lián)系在一起，通常用于最短/長(zhǎng)路的線性求解裸題：1191. 家譜樹(shù) 1191. 家譜樹(shù) - AcWing題庫(kù) 差分約束+拓?fù)渑判颍?192. 獎(jiǎng)金 1192. 獎(jiǎng)金 - AcWing題庫(kù) 由于圖中所有邊權(quán)都是正數(shù)，可以直接使用topsort求解差分約束問(wèn)題根據(jù)題意，要求一個(gè)最小值，使用最長(zhǎng)路求解
2024年02月12日
瀏覽(18)
第三章圖論 No.12歐拉回路與歐拉路徑
小學(xué)一筆畫問(wèn)題，每條邊只經(jīng)過(guò)一次判斷圖是否存在歐拉回路：判斷圖是否連通（存在孤立邊），再根據(jù)有向/無(wú)向具體判斷對(duì)于無(wú)向圖來(lái)說(shuō)，歐拉路徑中，起點(diǎn)和終點(diǎn)的度數(shù)為奇數(shù)，中間點(diǎn)的度數(shù)為偶數(shù) 起點(diǎn)和終點(diǎn)：開(kāi)始和結(jié)束時(shí)必須經(jīng)過(guò)一條邊，其余情況為：從一條邊
2024年02月12日
瀏覽(23)
第三章圖論 No.1單源最短路及其綜合應(yīng)用
做乘法的最短路時(shí)，若權(quán)值=0，只能用spfa來(lái)做，相等于加法中的負(fù)權(quán)邊 1129. 熱浪 1129. 熱浪 - AcWing題庫(kù) 單源最短路，稀疏圖，用堆優(yōu)化Dijkstra即可，就是板子套了個(gè)背景 debug：由于是無(wú)向圖，邊的數(shù)量要開(kāi)兩倍。但是 w[N] 沒(méi)改，debug了很久所以 e[M], ne[M], w[M] ，只有 h[N] ，其他
2024年02月14日
瀏覽(21)
第三章圖論 No.10無(wú)向圖的雙連通分量
無(wú)向圖有兩種雙連通分量邊雙連通分量，e-DCC 點(diǎn)雙連通分量，v-DCC 橋：刪除這條無(wú)向邊后，圖變得不連通，這條邊被稱為橋邊雙連通分量：極大的不含有橋的連通區(qū)域，說(shuō)明無(wú)論刪除e-DCC中的哪條邊，e-DCC依舊連通（該連通分量的任意邊屬于原圖中的某條環(huán)）。此外，任意兩
2024年02月12日
瀏覽(16)
第三章圖論 No.4最小生成樹(shù)的簡(jiǎn)單應(yīng)用
存在邊權(quán)為負(fù)的情況下，無(wú)法求最小生成樹(shù) 裸題：1140. 最短網(wǎng)絡(luò) 1140. 最短網(wǎng)絡(luò) - AcWing題庫(kù) 套個(gè)prim的板子即可裸題：1141. 局域網(wǎng) 1141. 局域網(wǎng) - AcWing題庫(kù) 裸題，稀疏圖，套個(gè)kruskal的板子就行需要注意的是：題目給定的圖可能存在多個(gè)連通塊，若使用prim算法，需要對(duì)每個(gè)連通
2024年02月14日
瀏覽(31)
第三章圖論 No.11二分圖，匈牙利算法與點(diǎn)覆蓋
257. 關(guān)押罪犯 - AcWing題庫(kù) 最大最小問(wèn)題，一眼二分答案的范圍在 [ 1 , 1 e 9 ] [1, 1e9] [ 1 , 1 e 9 ] 之間，二分答案，check(mid) check：將所有權(quán)值大于mid的邊進(jìn)行二分，若能得到二分圖，返回true，否則返回false 最終將得到最優(yōu)解ans，所有大于ans的邊組成的圖為二分圖，若是圖中有邊
2024年02月12日
瀏覽(19)
第三章圖論 No.8最近公共祖先lca, tarjan與次小生成樹(shù)
O ( m l o g n ) O(mlogn) O ( m l o g n ) ，n為節(jié)點(diǎn)數(shù)量，m為詢問(wèn)次數(shù)，lca是一種在線處理詢問(wèn)的算法自己也是自己的祖先倍增： f a ( i , j ) fa(i, j) f a ( i , j ) 表示從i開(kāi)始，向上走 2 j 2^j 2 j 步走到的點(diǎn) j = 0，走到父節(jié)點(diǎn) j 0，分兩步走，先走到 2 j ? 1 2^{j-1} 2 j ? 1 步再走 2 j ? 1 2^{
2024年02月13日
瀏覽(27)
第三章圖論 No.5最小生成樹(shù)之虛擬源點(diǎn)，完全圖與次小生成樹(shù)
虛擬源點(diǎn)：1146. 新的開(kāi)始 1146. 新的開(kāi)始 - AcWing題庫(kù) 與一般的最小生成樹(shù)問(wèn)題不同，本題需要在建立電站的電井之間建立電網(wǎng)，在兩個(gè)電站之間建立電網(wǎng)需要花費(fèi)金額，可以看成一條具有權(quán)值的邊但是建立電網(wǎng)的前提是：其中一個(gè)電井需要建立電站，建立電站也需要費(fèi)用已經(jīng)
2024年02月14日
瀏覽(24)
第三章圖論 No.3 flody之多源匯最短路，傳遞閉包，最小環(huán)與倍增
flody的四個(gè)應(yīng)用：多源匯最短路傳遞閉包找最小環(huán) 恰好經(jīng)過(guò)k條邊的最短路倍增多源匯最短路：1125. 牛的旅行 1125. 牛的旅行 - AcWing題庫(kù) 直徑概念：同一連通塊中，兩個(gè)距離最遠(yuǎn)的點(diǎn)之間的距離如何求直徑？由于圖中存在著兩個(gè)連通塊，所以直接對(duì)全圖做一個(gè)flody，就能更
2024年02月14日
瀏覽(27)