拓扑排序专题篇

news/2024/12/22 9:01:04/

目录

前言

课程表

课程表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;}
};


http://www.ppmy.cn/news/1528250.html

相关文章

JWT跨域认证

JWT跨域认证

Session认证 用户认证的流程&#xff1a; 用户向服务器发送用户名和密码。 服务器验证通过后&#xff0c;在当前对话(session)里面保存相关数据&#xff0c;比如用户角色、登录时间等。 服务器向用户返回一个session_id,写入用户的Cookie。 用户随后的每一次请求&#xff0c;…
阅读更多...
导电滑环在工业设备中的作用分析

导电滑环在工业设备中的作用分析

导电滑环作为现代工业设备中的关键组件&#xff0c;广泛应用于各种机械和电子系统中。本文将探讨导电滑环的工作原理及其在不同应用领域中的重要作用。 导电滑环的工作原理主要基于电气传导与机械旋转的结合。导电滑环通常由环形导体和刷子组成&#xff0c;刷子紧贴在滑环表面…
阅读更多...
前缀和与差分（二维）

前缀和与差分（二维）

二维前缀和 下面是一个二维数组&#xff0c;我们要求&#xff08;1&#xff0c;1&#xff09;到&#xff08;2&#xff0c;2&#xff09;区间内的所有元素的和&#xff0c;最原始的方法就是遍历每个元素然后一个一个加起来&#xff0c;此时时间复杂度为O(n*m)。 我们之前学过…
阅读更多...
下载 B 站封面的正确方式

下载 B 站封面的正确方式

B 友们经常用一些很好看的图片作为视频封面&#xff0c;但是大部分都不会指出图片来源&#xff0c;为此我们可以下载封面原图&#xff0c;用于保存或者搜索源出处。 这里介绍几个我知道的方法&#xff0c;欢迎补充&#x1f914; ‍ 使用相关客户端 上一篇博客介绍了很多的能…
阅读更多...
【C++篇】~类和对象（中）

【C++篇】~类和对象（中）

类和对象&#xff08;中&#xff09; 1.类的默认成员函数​ 默认成员函数就是用户没有显式实现&#xff0c;编译器会自动生成的成员函数称为默认成员函数。一个类&#xff0c;我们不写的情况下编译器会默认生成以下6个默认成员函数&#xff0c;需要注意的是这6个中最重要的是前…
阅读更多...
k8s证书过期处理

k8s证书过期处理

证书一共分为 根CA&#xff08;ca.crt&#xff09; master各组件的证书&#xff08;包括etcd、apiserver、front-proxy、controller-manager等各种&#xff09; kubelet证书 k8s证书有效期说明&#xff1a; 1、原生版本有效期master节点&#xff1a; /etc/kubernetes/ssl/…
阅读更多...
Node js介绍

Node js介绍

目录 概要**对Node的认识****Node的概念理解****Node和浏览器区别****Node的架构图** **Node的应用场景****Node的安装****安装Node的LTS版本****Node的版本管理工具nvm(了解)** **Node的输入和输出**Node程序传递参数Node的输出 **Node的全局对象****特殊的全局对象****其他的…
阅读更多...
[ffmpeg] 视频格式转换

[ffmpeg] 视频格式转换

本文主要梳理 ffmpeg 中的视频格式转换。由于上屏的数据是 rgba&#xff0c;编码使用的是 yuv数据&#xff0c;所以经常会使用到视频格式的转换。 除了使用 ffmpeg进行转换&#xff0c;还可以通过 libyuv 和 directX 写 shader 进行转换。 之前看到文章说 libyuv 之前是 ffmpeg…
阅读更多...
最新文章

Copyright @ 2022~2023