LCR113-LCR115拓扑排序

剑指offer（专项突破版）15.3 拓扑排序

LCR113.课程排序

分析

将课程看成图中的节点，如果两门课程存在先修顺序那么它们在图中对应的节点之间存在一条从先修课程到后修课程的边，因此这是一个有向图。

对有向图进行拓扑排序的算法是每次找出一个入度为0的节点添加到序列中，然后删除该节点及所有以该节点为起点的边。重复这个过程，直到图为空或图中不存在入度为0的节点。

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        // 构建有向图，键是先修课程，它的值是必须在键对应的课程之后学习的所有课程
        unordered_map<int, vector<int>> hashmap;
        for(int i = 0; i < numCourses; i++){
            vector<int> temp;
            hashmap[i] = temp;
        }
        // 初始化图和入度数组
        vector<int> inDegree(numCourses, 0);
        for(auto& preq : prerequisites){
            hashmap[preq[1]].push_back(preq[0]);
            inDegree[preq[0]]++;
        }
        // 定义队列，并把入度为0的加入到队列中
        queue<int> que;
        for(int i = 0; i < numCourses; i++){
            if(inDegree[i] == 0){
                que.push(i);
            }
        }
        // 定义数组，不断加入删除的节点
        vector<int> order;
        while(!que.empty()){
            int course = que.front();
            que.pop();
            order.push_back(course);
            // 删除course，即对于course出发的节点，入度-1
            for(int next : hashmap[course]){
                inDegree[next]--;
                if(inDegree[next] == 0){
                    que.push(next);
                }
            }
        }
        // 判断最后的图是否为空
        return order.size() == numCourses ? order : vector<int>();
    }
};

• 时间复杂度：O(v+e)
• 空间复杂度：O(v+e)

LCR114.火星词典

分析

如果已知两个字母的大小关系，那么图中就有一条从较小的字母指向较大的字母的边。如果能够得出该有向图的拓扑排序序列，那么任意一条边的起始节点（较小的字母）在拓扑排序序列中一定出现在终止节点（较大的字母）的前面。因此，这个问题实质上一个关于拓扑排序的问题。

class Solution {
public:
    string alienOrder(vector<string>& words) {
        // 定义图，键是字符，值是所有大于它的字符
        unordered_map<char, unordered_set<char>> graph;
        // 定义入度哈希表，键是字符，值是入度值
        unordered_map<char, int> inDegree;
        // 初始化
        for(string word : words){
            for(char ch : word){
                unordered_set<char> temp;
                graph[ch] = temp;
                inDegree[ch] = 0;
            }
        }
        // 对于每个单词
        for(int i = 1; i < words.size(); i++){
            string word1 = words[i-1];
            string word2 = words[i];
            // 如果w1<w2，但word2是word1的前缀，说明没有符合的顺序
            if(word1.size() > word2.size() && word1.substr(0, word2.size()) == word2){
                return "";
            }
            // 否则对于两个单词的每个字符
            for(int j = 0; j < word1.size() && j < word2.size(); j++){
                char ch1 = word1[j];
                char ch2 = word2[j];
                // 两个字符不相等，存在有向边
                if(ch1 != ch2){
                    if(!graph[ch1].count(ch2)){
                        // 更新图和入度
                        graph[ch1].insert(ch2);
                        inDegree[ch2]++;
                    }
                    // 后续字符不再需要比较
                    break;
                }
            }
        }
        // 定义队列，存放入度为0的字符
        queue<char> que;
        for(auto& kv : inDegree){
            if(kv.second == 0){
                que.push(kv.first);
            }
        }
        // 拓扑排序
        string res = "";
        while(!que.empty()){
            char ch = que.front();
            que.pop();
            res += ch;
            // 删除ch，从它出发的节点入度减一
            for(char next : graph[ch]){
                inDegree[next]--;
                if(inDegree[next] == 0){
                    que.push(next);
                }
            }
        }
        return res.size() == graph.size() ? res : "";
    }
};

• 时间复杂度：如果单词列表的长度为m，平均每个单词的长度为n，由于上述代码在构建有向图时需要扫描并比较每个字母，因此构建有向图的时间复杂度是O（mn）。该外星文的所有字母为英文字母。有向图中的节点为外星文的字母，最多只有26个，可以将其看成常数。最多根据单词列表words相邻的两个单词在图中添加一条边，所以边的数目是O（n）。于是，采用广度优先搜索的拓扑排序的时间复杂度是O（n）。综合来看，上述算法的总的时间复杂度是O（mn）。
• 空间复杂度：O(mn)

LCR115.序列重建

分析

如果得到的是有向图的拓扑排序序列，那么任意一条边的起始节点在拓扑排序序列中一定位于终止节点的前面。因此，由seqs重建的序列就是由seqs构建的有向图的拓扑排序的序列。这个问题就转变成判断一个有向图的拓扑排序序列是否唯一。

由于目标是判断图的拓扑排序序列是否唯一，而当某个时刻队列中的节点数目大于1时，就知道此时有多个入度为0的节点，那么按任意顺序排列这个入度为0的节点都能生成有效的拓扑排序序列，因此拓扑排序的序列不是唯一的。由此可知，只在队列的大小为1的时候重复添加入度为0的节点。

class Solution {
public:
    bool sequenceReconstruction(vector<int>& nums, vector<vector<int>>& sequences) {
        // 定义图和入度
        unordered_map<int, unordered_set<int>> graph;
        unordered_map<int, int> inDegree;
        
        // 初始化
        for(auto& seq : sequences){
            for(int num : seq){
                graph[num]; // 确保每个数都有一个图节点
                inDegree[num] = 0; // 初始化入度为0
            }
        }
        
        // 对于每个数字，建立图关系
        for(auto& seq : sequences){
            for(int i = 0; i < seq.size() - 1; i++){
                int num1 = seq[i];
                int num2 = seq[i+1];
                if(!graph[num1].count(num2)){
                    graph[num1].insert(num2);
                    inDegree[num2]++;
                }
            }
        }
        
        // 定义队列并初始化
        queue<int> que;
        for(auto& kv : inDegree){
            if(kv.second == 0){
                que.push(kv.first);
            }
        }
        
        // 拓扑排序
        vector<int> res;
        while(!que.empty()){
            if(que.size() > 1) return false; // 如果队列中有多个元素，说明不是唯一的
            int num = que.front();
            que.pop();
            res.push_back(num);
            // 对所有邻接节点
            for(int next : graph[num]){
                inDegree[next]--;
                if(inDegree[next] == 0){
                    que.push(next);
                }
            }
        }
        
        return vectorsAreEqual(nums, res);
    }

    bool vectorsAreEqual(vector<int>& v1, vector<int>& v2) {
        // 检查大小是否相同
        if (v1.size() != v2.size()) {
            return false;
        }
        // 利用 std::equal 比较元素
        return equal(v1.begin(), v1.end(), v2.begin());
    }
};

• 时间复杂度：O(v+e)
• 空间复杂度：O(v+e)

总结

拓扑排序是指对一个有向无环图的节点进行排序之后得到的序列。如果存在一条从节点A指向节点B的边，那么在拓扑排序的序列中节点A出现在节点B的前面。一个有向无环图可以有一个或多个拓扑排序序列，但无向图或有环的有向图都不存在拓扑排序。节点v的入度指的是以节点v为终点的边的数目，而节点v的出度是指以节点v为起点的边的数目。

一种常用的拓扑排序算法是每次从有向无环图中取出一个入度为0的节点添加到拓扑排序序列之中，然后删除该节点及所有以它为起点的边。重复这个步骤，直到图为空或图中不存在入度为0的节点。如果最终图为空，那么图是有向无环图，此时就找到了该图的一个拓扑排序序列。如果最终图不为空并且已经不存在入度为0的节点，那么图中一定有环。