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

n <= 10

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

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

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;
            }
        }
    }
};