拓扑排序相关leetcode算法题

1.课程表

课程表

class Solution {
    //进行一次拓扑排序即可
public:
    bool canFinish(int n, vector<vector<int>>& prerequisites) {
        unordered_map<int,vector<int>> edges;//使用邻接表存图
        vector<int> in(n);//存储各个顶点的入度
        //1.建图
        for(auto& e: prerequisites)
        {
            int a = e[0],b=e[1];//b->a
            edges[b].push_back(a);
            in[a]++;
        }
        //2.一次BFS
        queue<int> q;
        for(int i=0;i<n;i++)
        {
            if(in[i]==0) q.push(i);
        }
        while(q.size())
        {
            auto t = q.front();q.pop();
            for(auto a:edges[t])
            {
                in[a]--;
                if(in[a] == 0) q.push(a);
            }
        }
        //3.判断
        for(int i=0;i<n;i++)
        {
            if(in[i]) return false;
        }
        return true;
    }
};

2.课程表II

课程表II

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> edges(numCourses);//使用邻接表存图
        vector<int> in(numCourses);//存储每个顶点的入度信息
        //1.建图
        for(auto& e:prerequisites)
        {
            int a = e[0],b=e[1];//b->a
            edges[b].push_back(a);
            in[a]++;
        }
        //2.进行拓扑排序
        queue<int> q;
        vector<int> ret;
        for(int i=0;i<numCourses;i++)
        {
            if(in[i] == 0)
            {
                q.push(i);
                ret.push_back(i);
            }
        }
        //3.一次BFS
        while(q.size())
        {
            auto t = q.front();q.pop();
            for(int a:edges[t])
            {
                in[a]--;
                if(in[a] == 0)
                {
                    q.push(a);
                    ret.push_back(a);
                }
            }
        }
        //4.判断
        if(ret.size() == numCourses) return ret;
        else return {};
    }
};

3.火星词典

火星词典

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;
        string ret;
        for(auto&[a,b] : in)
        {
            if(b==0) q.push(a);
        }
        //3.一次BFS
        while(q.size())
        {
            char t = q.front();q.pop();
            ret+=t;
            for(auto a: edges[t])
            {
                if(--in[a]==0) q.push(a);
            }
        }
        //4.判断
        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],b = s2[i];//a->b
                if(!edges.count(a) || !edges[a].count(b))
                {
                    edges[a].insert(b);
                    in[b]++;
                }
                break;
            }
        }
         //abc ab 如此的处理一下，不合法
        if(i==s2.size() && i<s1.size()) cheak = true;
    }
};