引言

這個(gè)拓?fù)渑判虼蠹覒?yīng)該都聽說過，用的地方也是很多，考研和面試也是經(jīng)?？迹鋵?shí)這個(gè)排序算法的思想比較簡單，應(yīng)用的話就是可以用來判斷一個(gè)圖中是否存在一個(gè)環(huán)，本文主要是介紹拓?fù)渑判虻乃枷耄约耙粋€(gè)簡單的模板題，來幫助了解什么是拓?fù)渑判?，以及怎么寫?/p>

一、拓?fù)渑判蚋拍?/h2>

英文名：topsort，叫拓?fù)渑判蚣儗偈且糇g，實(shí)際沒啥具體含義哈
只有有向圖無環(huán)圖存在拓?fù)湫蛄?/p>

思想：找入度為0的點(diǎn)加入序列，然后更新剩余的點(diǎn)，再找入度為零的點(diǎn)再次更新，直至圖中所有的點(diǎn)全部加入到序列中，然后加入序列的順序就是拓?fù)渑判虻捻樞蚶玻?br> 注：當(dāng)有多個(gè)入度為0的點(diǎn)時(shí)，順序隨便，所以一個(gè)圖的拓?fù)渑判?strong>不是唯一的！

二、代碼模板

const int N = 1e5+10;

int n, m;
int h[N], e[N], ne[N], idx;  //常規(guī)的鏈?zhǔn)酱鎯?chǔ)法
int dist[N], q[N];  //dist[i]代表i號點(diǎn)的入度數(shù)

bool topsort()
{
    int hh = 0, tt = -1;
    
    for(int i = 1; i <= n; ++i)  //先把所有入度為0的點(diǎn)加入序列中
    {
        if(!dist[i]) q[++tt] = i;
    }
    
    while(hh <= tt)
    {
        auto t = q[hh++];
        
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            dist[j]--;  //將其與之相連點(diǎn)的入度減1
            if(!dist[j]) q[++tt] = j;  //若入度減為0則加入到隊(duì)列中
        }
    }
    
    return tt == n - 1;  //若所有點(diǎn)都加入隊(duì)列中，說明存在拓?fù)湫蛄?/span>
}

//輸出拓?fù)湫蛄校瑒偤脼榧尤氲疥?duì)列的順序
if(topsort())
{
    for(int i = 0; i < n; ++i) printf("%d ", q[i]);
}

三、例題

給定一個(gè) n 個(gè)點(diǎn) m 條邊的有向圖，點(diǎn)的編號是 1到 n，圖中可能存在重邊和自環(huán)。

請輸出任意一個(gè)該有向圖的拓?fù)湫蛄校绻負(fù)湫蛄胁淮嬖?，則輸出 ?1。

若一個(gè)由圖中所有點(diǎn)構(gòu)成的序列 A 滿足：對于圖中的每條邊 (x,y)，x在 A 中都出現(xiàn)在 y 之前，則稱 A 是該圖的一個(gè)拓?fù)湫蛄小?
輸入格式
第一行包含兩個(gè)整數(shù) n 和 m。
接下來 m 行，每行包含兩個(gè)整數(shù) x 和 y，表示存在一條從點(diǎn) x 到點(diǎn) y 的有向邊 (x,y)。

輸出格式
共一行，如果存在拓?fù)湫蛄?，則輸出任意一個(gè)合法的拓?fù)湫蛄屑纯伞?否則輸出 ?1。

數(shù)據(jù)范圍
1≤n,m≤105

輸入樣例：
3 3
1 2
2 3
1 3
輸出樣例：
1 2 3

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 1e5+10;

int n, m;
int h[N], e[N], ne[N], idx;
int dist[N], q[N];

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

bool topsort()
{
    int hh = 0, tt = -1;
    
    for(int i = 1; i <= n; ++i)
    {
        if(!dist[i]) q[++tt] = i;
    }
    
    while(hh <= tt)
    {
        auto t = q[hh++];
        
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            dist[j]--;  
            
            if(!dist[j]) q[++tt] = j;
        }
    }
    
    return tt == n - 1;
}

int main()
{
    memset(h, -1, sizeof h);
    
    scanf("%d%d", &n, &m);
    
    while(m--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a,b);
        dist[b]++;
    }
    
    if(!topsort()) puts("-1");
    else for(int i = 0; i < n; ++i) printf("%d ", q[i]);
    
    return 0;
}

看一個(gè)用例還是可以的，然后這道題也AC了
文章來源地址http://www.zghlxwxcb.cn/news/detail-795427.html

到了這里，關(guān)于算法學(xué)習(xí)系列（二十一）：拓?fù)渑判虻奈恼戮徒榻B完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！