②是否存在環(huán)：若拓?fù)湫蛄袛?shù)組大小等于節(jié)點(diǎn)總個(gè)數(shù)則說明圖中無環(huán)；反之，這說明圖有環(huán)

二、代碼模板

/*這里用課程表一題的代碼當(dāng)作模板*/
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> g(numCourses);
        int in_degree[numCourses];   //記錄節(jié)點(diǎn)的入度
        memset(in_degree, 0, sizeof(in_degree));
        for (auto& e : prerequisites) {
            int x = e[0], y = e[1];    //建圖
            g[x].push_back(y);
            in_degree[y]++;     // x -> y ，則y節(jié)點(diǎn)入度+1
        }
        vector<int> order;
        queue<int> q;
        for(int i = 0; i < numCourses; i++) if (in_degree[i] == 0) q.push(i);    //將入度為0的節(jié)點(diǎn)加入到隊(duì)列中
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            order.push_back(x);    //push到拓?fù)湫蛄兄?            for (auto y : g[x]) {
                in_degree[y]--;     //x -> y , 即將y入度-1
                if (in_degree[y] == 0) q.push(y);
            }
        }
        return order.size() == numCourses;   //判斷是否有環(huán)
    }
};

三、練習(xí)

1、210.課程表Ⅱ??

現(xiàn)在你總共有?numCourses?門課需要選，記為?0?到?numCourses - 1。給你一個(gè)數(shù)組?prerequisites?，其中?prerequisites[i] = [ai, bi]?，表示在選修課程?ai?前?必須?先選修?bi?。

• 例如，想要學(xué)習(xí)課程?0?，你需要先完成課程?1?，我們用一個(gè)匹配來表示：[0,1]?。

返回你為了學(xué)完所有課程所安排的學(xué)習(xí)順序?？赡軙卸鄠€(gè)正確的順序，你只要返回?任意一種?就可以了。如果不可能完成所有課程，返回?一個(gè)空數(shù)組?。

示例：

輸入：numCourses = 2, prerequisites = [[1,0]]
輸出：[0,1]
解釋：總共有 2 門課程。要學(xué)習(xí)課程 1，你需要先完成課程 0。因此，正確的課程順序?yàn)?[0,1] 。

解題思路： 與課程表Ⅰ思路基本一樣，依次取出入度為0的節(jié)點(diǎn)加入到答案數(shù)組中，若數(shù)組大小與總結(jié)點(diǎn)個(gè)數(shù)不相同，則說明圖中有環(huán)，返回空數(shù)組。

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> g(numCourses);
        int in_degree[numCourses];
        memset(in_degree, 0, sizeof(in_degree));
        for (auto& e : prerequisites) {
            int x = e[1], y = e[0];
            g[x].push_back(y);
            in_degree[y]++;
        }
        vector<int> order;
        queue<int> q;
        for(int i = 0; i < numCourses; i++) if (in_degree[i] == 0) q.push(i);
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            order.push_back(x);
            for (auto y : g[x]) {
                in_degree[y]--;
                if (in_degree[y] == 0) q.push(y);
            }
        }
        return order.size() == numCourses ? order : vector<int>();
    }
};

2、2392.給定條件下構(gòu)造舉證??

給你一個(gè)?正?整數(shù)?k?，同時(shí)給你：

• 一個(gè)大小為?n?的二維整數(shù)數(shù)組?rowConditions?，其中?rowConditions[i] = [abovei, belowi]?
• 一個(gè)大小為?m?的二維整數(shù)數(shù)組?colConditions?，其中?colConditions[i] = [lefti, righti]?。

兩個(gè)數(shù)組里的整數(shù)都是?1?到?k?之間的數(shù)字。

你需要構(gòu)造一個(gè)?k x k?的矩陣，1?到?k?每個(gè)數(shù)字需要?恰好出現(xiàn)一次?。剩余的數(shù)字都是?0?。

矩陣還需要滿足以下條件：

• 對于所有?0?到?n - 1?之間的下標(biāo)?i?，數(shù)字?abovei?所在的?行?必須在數(shù)字?belowi?所在行的上面。
• 對于所有?0?到?m - 1?之間的下標(biāo)?i?，數(shù)字?lefti?所在的?列?必須在數(shù)字?righti?所在列的左邊。

返回滿足上述要求的?任意?矩陣。如果不存在答案，返回一個(gè)空的矩陣。

示例：

輸入：k = 3, rowConditions = [[1,2],[3,2]], colConditions = [[2,1],[3,2]]
輸出：[[3,0,0],[0,0,1],[0,2,0]]
解釋：上圖為一個(gè)符合所有條件的矩陣。
行要求如下：
- 數(shù)字 1 在第 1 行，數(shù)字 2 在第 2?行，1 在 2 的上面。
- 數(shù)字 3 在第 0?行，數(shù)字 2 在第 2?行，3 在 2 的上面。
列要求如下：
- 數(shù)字 2 在第 1?列，數(shù)字 1 在第 2?列，2 在 1 的左邊。
- 數(shù)字 3 在第 0?列，數(shù)字 2 在第 1?列，3 在 2 的左邊。
注意，可能有多種正確的答案。

解題思路：該題很明顯是處理先后的問題，我們分別處理行與列，分別得到行與列拓?fù)湫蛄校詈笸ㄟ^一個(gè)數(shù)組轉(zhuǎn)換，將下標(biāo)作為節(jié)點(diǎn)，對應(yīng)的值作為該節(jié)點(diǎn)位于行/列的位置；

class Solution {
public:
    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {
        vector<int> roworder, colorder;
        function<bool(vector<vector<int>>&, vector<int>&)> topo_sort = [&](vector<vector<int>>& edge, vector<int>& order) -> bool{
            vector<vector<int>> g(k);
            int in_deg[k];
            memset(left, 0, sizeof(left));
            for (auto& e : edge) {
                int x = e[0]-1, y = e[1] - 1;
                g[x].push_back(y);
                in_deg[y]++;
            }

            queue<int> q;
            for(int i = 0; i < k; i++) if (in_deg[i] == 0) q.push(i);
            while (!q.empty()) {
                int x = q.front();
                q.pop();
                order.push_back(x);
                for (auto y : g[x]) {
                    in_deg[y]--;
                    if (in_deg[y] == 0) q.push(y);
                }
            }
            return order.size() == k;
        };

        vector<vector<int>> ans(k, vector<int>(k, 0));
        if (!topo_sort(rowConditions, roworder) || !topo_sort(colConditions, colorder)) return {};
        int row[k], col[k];
        for (int i = 0; i < k; i++) {
            row[roworder[i]] = i;
            col[colorder[i]] = i;
        }
        for (int i = 0; i < k; i++) {
            ans[row[i]][col[i]] = i + 1;
        }
        return ans;
    }
};

3、310.最小高度樹??

樹是一個(gè)無向圖，其中任何兩個(gè)頂點(diǎn)只通過一條路徑連接。 換句話說，一個(gè)任何沒有簡單環(huán)路的連通圖都是一棵樹。

給你一棵包含?n?個(gè)節(jié)點(diǎn)的樹，標(biāo)記為?0?到?n - 1?。給定數(shù)字?n?和一個(gè)有?n - 1?條無向邊的?edges?列表（每一個(gè)邊都是一對標(biāo)簽），其中?edges[i] = [ai, bi]?表示樹中節(jié)點(diǎn)?ai?和?bi?之間存在一條無向邊。

可選擇樹中任何一個(gè)節(jié)點(diǎn)作為根。當(dāng)選擇節(jié)點(diǎn)?x?作為根節(jié)點(diǎn)時(shí)，設(shè)結(jié)果樹的高度為?h?。在所有可能的樹中，具有最小高度的樹（即，min(h)）被稱為?最小高度樹?。

請你找到所有的?最小高度樹?并按?任意順序?返回它們的根節(jié)點(diǎn)標(biāo)簽列表。

樹的?高度?是指根節(jié)點(diǎn)和葉子節(jié)點(diǎn)之間最長向下路徑上邊的數(shù)量。

示例：

輸入：n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
輸出：[3,4]

解題思路： 本題思路較為復(fù)雜，可以大致理解為貪心，證明過程可以參考力扣官方答案。每次去掉節(jié)點(diǎn)入度最小的節(jié)點(diǎn)，到最后剩余1-2個(gè)節(jié)點(diǎn)即為可以作為最小高度樹的根節(jié)點(diǎn)

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if (n == 1) return {0};
        unordered_map<int, vector<int>> g;
        vector<int> degree(n);
        for (auto& e : edges) {
            int x = e[0], y = e[1];
            g[x].push_back(y);
            g[y].push_back(x);
            degree[x]++;
            degree[y]++;
        }        

        vector<int> ans;
        queue<int> q;
        for (int i = 0; i < n; i++) if (degree[i] == 1) q.push(i);
        while(!q.empty()) {
            vector<int> tmp;
            int size = q.size();
            while(size--) {
                int x = q.front();
                q.pop();
                tmp.push_back(x);
                for(auto y : g[x]) {
                    if (--degree[y] == 1) q.push(y);
                }
            }
            ans = move(tmp);
        }
        return ans;
    }
};

4、2603.收集樹中金幣 ??

給你一個(gè)?n?個(gè)節(jié)點(diǎn)的無向無根樹，節(jié)點(diǎn)編號從?0?到?n - 1?。給你整數(shù)?n?和一個(gè)長度為?n - 1?的二維整數(shù)數(shù)組?edges?，其中?edges[i] = [ai, bi]?表示樹中節(jié)點(diǎn)?ai?和?bi?之間有一條邊。再給你一個(gè)長度為?n?的數(shù)組?coins?，其中?coins[i]?可能為?0?也可能為?1?，1?表示節(jié)點(diǎn)?i?處有一個(gè)金幣。

一開始，你需要選擇樹中任意一個(gè)節(jié)點(diǎn)出發(fā)。你可以執(zhí)行下述操作任意次：

• 收集距離當(dāng)前節(jié)點(diǎn)距離為?2?以內(nèi)的所有金幣，或者
• 移動到樹中一個(gè)相鄰節(jié)點(diǎn)。

你需要收集樹中所有的金幣，并且回到出發(fā)節(jié)點(diǎn)，請你返回最少經(jīng)過的邊數(shù)。

如果你多次經(jīng)過一條邊，每一次經(jīng)過都會給答案加一。

示例 1：

輸入：coins = [0,0,0,1,1,0,0,1], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[5,6],[5,7]]
輸出：2
解釋：從節(jié)點(diǎn) 0 出發(fā)，收集節(jié)點(diǎn) 4 和 3 處的金幣，移動到節(jié)點(diǎn) 2 處，收集節(jié)點(diǎn) 7 處的金幣，移動回節(jié)點(diǎn) 0 。

?解題思路：

步驟1：?持續(xù)刪除沒有金幣的子樹，若該子樹沒有金幣，那么也就沒有必要訪問這個(gè)子樹的所有節(jié)點(diǎn)（拓?fù)渑判蛩悸?，記錄各個(gè)節(jié)點(diǎn)的入度）

步驟2：?因?yàn)榭梢詮囊粋€(gè)節(jié)點(diǎn)查詢到離該節(jié)點(diǎn)距離為2的所有節(jié)點(diǎn)，所以可以將這些可以其他節(jié)點(diǎn)間接訪問的節(jié)點(diǎn)刪除；通過連續(xù)兩次循環(huán)，將每次入度為1的葉子節(jié)點(diǎn)刪除。

?步驟3：?通過上述兩個(gè)步驟，剩余節(jié)點(diǎn)的葉子節(jié)點(diǎn)為必須被訪問的節(jié)點(diǎn)，易證得，從任意節(jié)點(diǎn)開始訪問所有剩余葉子節(jié)點(diǎn)并返回最初節(jié)點(diǎn)所經(jīng)過得邊數(shù)均為最后這顆樹（通過步驟1、2刪除節(jié)點(diǎn)之后的樹）的邊數(shù)的兩倍。文章來源地址http://www.zghlxwxcb.cn/news/detail-671362.html

class Solution {
public:
    int collectTheCoins(vector<int>& coins, vector<vector<int>>& edges) {
        int n = coins.size();
        vector<vector<int>> g(n);
        //拓?fù)渑判蛩玫挠涗浫攵鹊臄?shù)組，在后面的循環(huán)中可以得知，入度減為-1的節(jié)點(diǎn)即為刪除的節(jié)點(diǎn)
        vector<int> indegree(n);         
        for (auto& e : edges) {
            int x = e[0], y = e[1];
            g[x].push_back(y); g[y].push_back(x);
            indegree[x]++; indegree[y]++;
        }

        //步驟1
        queue<int> q;
        for (int i = 0; i < n; i++) if (coins[i] == 0 && indegree[i] == 1) q.push(i);
        while(!q.empty()) {
            int x = q.front();
            q.pop();
            indegree[x]--;
            for (auto y : g[x]) {
                indegree[y]--;
                若當(dāng)y為當(dāng)前樹的葉子節(jié)點(diǎn)且沒有金幣，則加入隊(duì)列中，繼續(xù)循環(huán)刪除
                if (indegree[y] == 1 && coins[y] == 0) q.push(y);  
            }
        }

        //步驟2
        for(int i = 0; i < n; i++) if (coins[i] == 1 && indegree[i] == 1) q.push(i);
        int t = 2;
        while(t--) {
            int size = q.size();
            while(size--) {
                int x = q.front();
                q.pop();
                indegree[x]--;
                for (auto y : g[x]) {
                    indegree[y]--;
                    if (indegree[y] == 1) q.push(y);
                }
            }
        }

        //步驟3：
        int st = -1;    //尋找dfs的入口
        for (int i = 0; i < n; i++) if (indegree[i] > 0) {
            st = i;
            break;
        }
        vector<int> vis(n, 0);
        int ans = 0;
        function<void(int)> dfs = [&](int x) -> void {
            vis[x] = true;
            for (auto y : g[x]) {
                if (indegree[y] > 0 && !vis[y]) {        //indegree[i] <= 0 表示該節(jié)點(diǎn)已刪除
                    vis[y] = true;
                    ans++;
                    dfs(y);
                }
            }
        };
        if (st != -1) dfs(st);
        return ans * 2;
    }
};

到了這里，關(guān)于?算法進(jìn)階?圖論::拓?fù)渑判?Topological Sorting)——快速理解到熟練運(yùn)用的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！