目錄
拓撲排序
1.如何排序？
2.如何形成拓撲排序?
3.如何建圖
1.看數據稠密度
2. 根據算法流程靈活建圖
1.課程表
2.課程表2
3.火星詞典
拓撲排序
找到做事情的先后順序，拓撲排序的結果可能不是唯一的
1.如何排序？
1.找出圖中入度為0的點，然后輸出
2.刪除與該點連接的邊
3.重復1.2操作，直到圖中沒有點? ?或者? ?圖中沒有度為0的點為止（因為有可能有環）
2.如何形成拓撲排序?
?借助隊列，來一次bfs即可
1.初始化：把所有入度為0的點加入隊列中即可
2.當隊列不為空的時候：
a.拿出隊頭元素，加入到最終結果中
b.刪除與該元素相連的邊
c.判斷 與刪除邊相連的點，是否入度變成0
如果入度為0，加入到隊列中
3.如何建圖
我們應該靈活使用stl里面的容器
?
?
1.看數據稠密度
我們可以用鄰接矩陣和鄰接表
鄰接表我們可以使用vector嵌套vector，也可以使用哈希表，其中哈希表比較通用一些。
?
2. 根據算法流程靈活建圖
?比如要統計每個節點的入度 我們用一個vector<int> 來統計
1.課程表
?207. 課程表 - 力扣（LeetCode）
class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {//1.準備工作unordered_map<int, vector<int>> edges;//鄰接表存圖vector<int> in(numCourses); // 標記每一個定義的入度//2.建圖for(auto& e: prerequisites){int a = e[0];int b = e[1];edges[b].push_back(a);in[a]++;}//3.拓撲排序queue<int> q;//a.把所有入度為0的點加入到隊列中for(int i = 0; i < numCourses; i++){if(in[i] == 0)q.push(i);}//b.bfswhile(q.size()){int t = q.front();q.pop();for(int a: edges[t]){in[a]--;if(in[a] == 0)q.push(a);}}//4.判斷是否有環for(int i = 0; i < numCourses; i++){if(in[i])return false;}return true;}
};2.課程表2
LCR 113. 課程表 II - 力扣（LeetCode）
只需要在pop的時候把相應元素加入數組中即可
class Solution {
public:vector<int> findOrder(int n, vector<vector<int>>& prerequisites) {unordered_map<int, vector<int>> hash;vector<int> in(n,0);vector<int> ret;vector<int> ret2;for(auto e:prerequisites){int a = e[0];int b = e[1];//b->ahash[b].push_back(a);in[a]++;}queue<int> q;for(int i = 0; i < n; i++){if(in[i] == 0)q.push(i);}while(q.size()){int t = q.front();ret.push_back(t);q.pop();for(auto e: hash[t]){in[e]--;if(in[e] == 0)q.push(e);}}for(auto e: in){if(e)return ret2;}return ret;}
};3.火星詞典
LCR 114. 火星詞典 - 力扣（LeetCode）?
如何搜集信息？兩層for循環
拓撲排序
1.建圖
我們采用兩層哈希嵌套hash<char, hash<char>> edges.
2.統計入度信息
hash<char, int> in
必須要初始化， 不然剛開始的時候找不到入度為0的值。（遍歷一下每個字符串即可）
3.如何收集信息
雙指針
4.細節問題
一些特殊子串一定是排在對應字符串前面的
出現下面這種情況 我們直接返回空
class Solution {unordered_map<char, unordered_set<char>> edges;//鄰接表存儲圖unordered_map<char, int> in; //統計入度bool cheak; // 處理邊界情況
public:string alienOrder(vector<string>& words) {//1.初始化哈希表 + 建圖for(auto& s: words){for(auto ch : s){in[ch] = 0;}}int n = words.size();for(int i = 0; i < n; i++){for(int j = i + 1; j < n; j++){add(words[i], words[j]);if(cheak)return "";}}//2.拓撲排序queue<char> q;for(auto& [a, b] : in){if(b == 0)q.push(a);}string ret;while(q.size()){char t = q.front();q.pop();ret += t;for(char ch: edges[t]){if(--in[ch] == 0)q.push(ch);}}//3.判斷for(auto& [a, b] : in){if(b != 0)return "";}return ret;}void add(string& s1, string& s2){int n = min(s1.size(), s2.size());int i = 0;for(; i < n; i++){if(s1[i] != s2[i]){char a = s1[i];char b = s2[i];// a->bif(!edges.count(a) || !edges[a].count(b)){edges[a].insert(b);in[b]++;}break;}}if(i == s2.size() && i < s1.size())cheak = true;}
};?
)
