拓扑排序专题篇

ops/2024/11/14 15:07:08/

目录

前言

课程表

课程表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/ops/113661.html

相关文章

Linux(ubuntu)Makefile

Linux(ubuntu)Makefile

一、Makefile简介 Makefile的必要性:嵌入式开发要将Linux移植到开发版上&#xff0c;而开发版没有图形界面。只能用终端&#xff0c;我们可以用gcc&#xff0c;但是很不方便。而Makefile能解决这个问题。 二、Makefile下载 终端输入:sudo apt install -y build-essential 三…
阅读更多...
javascript检测数据类型的方法

javascript检测数据类型的方法

1. typeof 运算符 typeof是一个用来检测变量的基本数据类型的运算符。它可以返回以下几种类型的字符串&#xff1a;“undefined”、“boolean”、“number”、“string”、“object”、“function” 和 “symbol”&#xff08;ES6&#xff09;。需要注意的是&#xff0c;对于 n…
阅读更多...
C语言程序设计（进阶）

C语言程序设计（进阶）

上了生活的贼船&#xff0c;那就做一个快乐的海盗。 2.3练习 下面代码输出的结果是什么&#xff1f; #include <stdio.h> int main() { char a -1; signed char b -1; unsigned char c -1; printf("a%d,b%d,c%d",a,b,a); return 0; } 解析&#xff…
阅读更多...
无人机飞手教员培训及就业分析

无人机飞手教员培训及就业分析

无人机飞手教员培训是一个综合性的教育体系&#xff0c;旨在培养具备专业飞行技能、扎实理论知识以及高效教学能力的无人机飞手导师。培训内容广泛覆盖从无人机基础知识到高级飞行技巧&#xff0c;再到教学方法与技巧&#xff0c;确保学员能够全面掌握无人机操作与教学的精髓。…
阅读更多...
焦化行业的变革力量：智能巡检机器人

焦化行业的变革力量：智能巡检机器人

根据相关数据&#xff0c;2024年1-2月份&#xff0c;焦炭产量为8039.5万吨&#xff0c;同比增长2.1%&#xff0c;这表明&#xff0c;我国焦化行业仍是全球最大的焦炭生产国和消费国&#xff0c;其市场规模占据了重要地位。焦化企业主要集中在山西省&#xff0c;其合计焦炭产能约…
阅读更多...
Unity多语言插件I2 Localization国际化应用

Unity多语言插件I2 Localization国际化应用

【就不收费了&#xff0c;要个关注不过分吧】 【图片来自插件官网&#xff0c;侵删】 前言 目前游戏往往都不会仅局限于国内语言&#xff0c;为了适应产品都要做国际化适配&#xff0c;因此会用到这个插件&#xff0c;这个插件要付费&#xff0c;因此请前往unity官网进行下载…
阅读更多...
php环境搭建教程（超详细）

php环境搭建教程（超详细）

要搭建一个PHP环境&#xff0c;你可以通过多种方式来进行配置&#xff0c;下面我将提供一个从零开始的详细教程&#xff0c;适用于想在Windows、Mac或Linux上搭建PHP环境的小白用户。我们会逐步讲解如何搭建PHP环境&#xff0c;使用常见的集成开发环境&#xff08;如XAMPP、MAM…
阅读更多...
Spring Boot-自动配置问题

Spring Boot-自动配置问题

**### Spring Boot自动配置问题探讨 Spring Boot 是当前 Java 后端开发中非常流行的框架&#xff0c;其核心特性之一便是“自动配置”&#xff08;Auto-Configuration&#xff09;。自动配置大大简化了应用开发过程&#xff0c;开发者不需要编写大量的 XML 配置或是繁琐的 Jav…
阅读更多...
最新文章

Copyright @ 2022~2023