天池 在线编程 课程表（拓扑排序 + 回溯）

文章目录

• 1. 题目
• 2. 解题

1. 题目

总共有n个课程，从0到n-1。 有些课程可能有先决条件，例如，你想修课程0，你必须先修一门课程1，这两门课之间的关系表示为:[0,1]

给定课程的总数和先决条件对的列表，返回你可以得到所有课程的不同方法的数量。

代码语言：javascript复制

n <= 10

样例1
输入:
n = 2
prerequisites = [[1,0]]
输出: 1
说明:
你必须按照0->1的顺序上课。

样例2
输入:
n = 2
prerequisites = []
Output: 2
输出:
你可以按0->1或1->0的顺序上课。

2. 解题

• 建图，记录出入度
• n 比较小，dfs 搜索

代码语言：javascript复制

class Solution {
public:
    /**
     * @param n: an integer, denote the number of courses
     * @param p: a list of prerequisite pairs
     * @return: return an integer,denote the number of topologicalsort
     */
    int ans = 0;
    int topologicalSortNumber(int n, vector<vector<int>> &p) {
        // Write your code here
        vector<int> indegree(n, 0);
        vector<bool> vis(n, false);
        vector<vector<int>> g(n);
        for(auto& pi : p)
        {
            indegree[pi[0]]  ;
            g[pi[1]].push_back(pi[0]);
        }
        dfs(g, vis, indegree, 0);
        return ans;
    }
    void dfs(vector<vector<int>> &g, vector<bool>& vis, vector<int> &indegree, int count)
    {
        if(count == g.size())
        {
            ans  ;
            return;
        }
        for(int i = 0; i < g.size(); i  )
        {
            if(vis[i]) continue;
            if(indegree[i]==0)
            {
                vis[i] = true;
                for(auto nt : g[i])
                    indegree[nt]--;
                dfs(g, vis, indegree, count 1);
                for(auto nt : g[i])
                    indegree[nt]  ;
                vis[i] = false;
            }
        }
    }
};

2490ms C

c++ dfs 搜索

0 人点赞