拓扑排序专题篇
目录
前言
课程表
课程表II
课程表IV
火星词典
前言
拓扑排序是指对一个有向无环图的节点进行排序之后得到的序列，如果存在一条从节点A指向节点B的边，那么在拓扑排序的序列中节点A出现在节点B的前面。一个有向无环图可以有一个或多个拓扑排序序列，但无向图或有向图都不存在拓扑排序。
一种常用的拓扑排序算法是每次从有向无环图中取出一个入度为0的节点添加到拓扑排序序列之中，然后删除该节点及所有以他为起点的边。重复这个步骤，直到图为空或图中不存在入度为0的节点。如果最终图为空，那么图是有向无环图，此时就找到了该图的一个拓扑排序序列。如果最终图不为空并且已经不存在入度为0的节点，那么该图一定有环。
课程表
题目
思路
首先先建图，可以采用邻接矩阵或者邻接表建图，解题时采用邻接表来建图，并统计每个节点的入度，然后扫描所有节点的入度，将入度尾0的节点加入到队列中，取出队头元素，将该节点加入数组中，并将以该节点为起始点的边的终点的入度-1，如果有节点的入度为0，就将该节点加入队列中，最后，如果数组的大小和课程数目不相等，说明存在环，不能修完课程；否则能修完课程。
代码
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<int> in(numCourses);
vector<vector<int>> vv(numCourses);
vector<int> v;
for(auto it:prerequisites){
vv[it[1]].push_back(it[0]);
in[it[0]]++;
}
queue<int> q;
for(int i=0;i<numCourses;i++)
if(in[i]==0) q.push(i);
while(!q.empty()){
int ret=q.front();
q.pop();
v.push_back(ret);
for(int x:vv[ret])
if(--in[x]==0)
q.push(x);
}
if(v.size()==numCourses) return true;
else return false;
}
};课程表II
题目
思路
这道题和上一道题其实是一样的，只不过是问题不同而已，解决方法还是首先先建图，可以采用邻接矩阵或者邻接表建图，解题时采用邻接表来建图，并统计每个节点的入度，然后扫描所有节点的入度，将入度尾0的节点加入到队列中，取出队头元素，将该节点加入数组中，并将以该节点为起始点的边的终点的入度-1，如果有节点的入度为0，就将该节点加入队列中，最后，如果数组的大小和课程数目不相等，说明存在环，不能修完课程；否则能修完课程。
代码
class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
unordered_map<int,vector<int>> hash;
vector<int> in(numCourses);
vector<int> ret;
for(auto it:prerequisites){
hash[it[1]].push_back(it[0]);
in[it[0]]++;
}
queue<int> q;
for(int i=0;i<numCourses;i++)
if(in[i]==0) q.push(i);
while(!q.empty()){
int top=q.front();q.pop();
ret.push_back(top);
for(int x:hash[top])
if(--in[x]==0)
q.push(x);
}
if(ret.size()==numCourses) return ret;
else return {};
}
};
// class Solution {
// public:
// vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
// vector<int> in(numCourses);
// vector<vector<int>> vv(numCourses);
// vector<int> ret;
// for(auto it:prerequisites){
// vv[it[1]].push_back(it[0]);
// in[it[0]]++;
// }
// queue<int> q;
// for(int i=0;i<numCourses;i++)
// if(in[i]==0) q.push(i);
// while(!q.empty()){
// int top=q.front();q.pop();
// ret.push_back(top);
// for(int x:vv[top])
// if(--in[x]==0)
// q.push(x);
// }
// if(ret.size()==numCourses) return ret;
// else return {};
// }
// };课程表IV
题目
思路
虽然这道题和前两道题看起来是一样的，但是这道题比前两道题要难一些，因为对于每一遍扫描到的入度为0的节点，这些节点之间是没有先决条件关系的，如果还用之前的解法，会把每一遍扫描到的入度为0的节点赋予先决条件，因此我们需要使用别的方法。
下面，先使用邻接表建图，然后扫描每个节点，进行深度优先遍历，如果该节点没有被遍历过，则遍历以该节点为起始点的所有边的终点，依旧是判断该节点有没有被遍历过，如果没有被遍历过，则遍历以该节点为起始点的所有边的终点，然后将邻接矩阵中的起始点到终点的值置为true，然后遍历所有终点，看是否存在以终点为起始点的点，然后将邻接矩阵中起始点到终点的终点的值置为isPre[pos][i]=isPre[pos][i]|isPre[x][i]。
代码
class Solution {
public:
vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
vector<vector<int>> edges(numCourses);
vector<bool> vis(numCourses,false);
vector<vector<bool>> isPre(numCourses,vector<bool>(numCourses,false));
for(auto& p:prerequisites)
edges[p[0]].push_back(p[1]);
for(int i=0;i<numCourses;i++)
dfs(edges,isPre,vis,i);
vector<bool> res;
for(auto& query:queries)
res.push_back(isPre[query[0]][query[1]]);
return res;
}
void dfs(vector<vector<int>>& edges,vector<vector<bool>>& isPre,vector<bool>& vis,int pos){
if(vis[pos]) return;
vis[pos]=true;
for(int x:edges[pos]){
dfs(edges,isPre,vis,x);
isPre[pos][x]=true;
for(int i=0;i<isPre.size();i++)
isPre[pos][i]=isPre[pos][i]|isPre[x][i];
}
}
};
//chatGpt的答案
// class Solution {
// public:
// vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
// vector<vector<int>> adjacencyList(numCourses);
// vector<vector<int>> successors(numCourses);
// vector<bool> visited(numCourses, false);
// unordered_map<int, int> topoOrderIndex; // Store the index of each course in topological order
// queue<int> q;
// // Construct adjacency list and initialize in-degree counts
// vector<int> inDegree(numCourses, 0);
// for (const auto& prerequisite : prerequisites) {
// int course = prerequisite[0];
// int prerequisiteCourse = prerequisite[1];
// adjacencyList[course].push_back(prerequisiteCourse);
// inDegree[prerequisiteCourse]++;
// }
// // Perform topological sort and record the order
// for (int i = 0; i < numCourses; ++i) {
// if (inDegree[i] == 0) {
// q.push(i);
// }
// }
// int topoIndex = 0;
// while (!q.empty()) {
// int current = q.front();
// q.pop();
// topoOrderIndex[current] = topoIndex++;
// for (int successor : adjacencyList[current]) {
// if (--inDegree[successor] == 0) {
// q.push(successor);
// }
// successors[current].push_back(successor);
// }
// }
// // Handle queries
// vector<bool> results;
// for (const auto& query : queries) {
// int courseA = query[0];
// int courseB = query[1];
// bool isPrerequisite = dfs(courseA, courseB, successors, visited, topoOrderIndex);
// results.push_back(isPrerequisite);
// fill(visited.begin(), visited.end(), false); // Reset visited for the next query
// }
// return results;
// }
// private:
// bool dfs(int courseA, int courseB, const vector<vector<int>>& successors, vector<bool>& visited, const unordered_map<int, int>& topoOrderIndex) {
// if (courseA == courseB) {
// return true;
// }
// visited[courseA] = true;
// for (int successor : successors[courseA]) {
// if (!visited[successor] && (topoOrderIndex.at(courseA) < topoOrderIndex.at(successor))) {
// if (successor == courseB || dfs(successor, courseB, successors, visited, topoOrderIndex)) {
// return true;
// }
// }
// }
// return false;
// }
// };火星词典
题目
思路
这道题的题目首先得看懂，然后解析所有字符串，两个字符串满足前一个字符串的前n个字符和后一个字符串的前n个字符相同，第一次出现不同字符时，前一个字符串的第n+1个字符的序列小于后一个字符串的第n+1个字符的序列，如果第一个字符串的长度大于第二个字符串的长度，且第一个字符串的长度为第二个字符串长度的字符和第二个字符串相等，这样是不符合题意的，直接返回空串；否则就建立邻接表，并统计所有节点的入度信息，将入度为0的节点的值加入队列，然后取出队头元素，将该节点加入字符串末尾，并将以该节点为起始点的边的终点的入度-1，如果有节点的入度为0，就将该节点加入队列中，执行将该节点加入字符串末尾，并将以该节点为起始点的边的终点的入度-1，如果有节点的入度为0，就将该节点加入队列中。
最后扫描数组，如果存在某个节点的入度不为0，说明存在环，不能排序，返回空串；否则返回结果字符串。
代码
class Solution {
unordered_map<char,unordered_set<char>> edges;
unordered_map<char,int> in;
bool flag;
public:
string alienOrder(vector<string>& words) {
for(string s:words)
for(char ch:s)
in[ch]=0;
int n=words.size();
for(int i=0;i<n-1;i++)
for(int j=i+1;j<n;j++){
helper(words[i],words[j]);
if(flag) return "";
}
queue<char> q;
string s;
for(auto& [a,b]:in){
if(b==0) q.push(a);
}
while(!q.empty()){
int ch=q.front();q.pop();
s+=ch;
for(char c:edges[ch])
if(--in[c]==0)
q.push(c);
}
for(auto& [a,b]:in)
if(b!=0) return "";
return s;
}
void helper(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],b=s2[i];
if(!edges.count(a) || !edges[a].count(b)){
edges[a].insert(b);
in[b]++;
}
break;
}
if(i==s2.size() && i<s1.size())
flag=true;
}
};