Luobuyu's Blog

0%

1462. 课程表 IV

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 3.3k 阅读时长 ≈ 3 分钟
使用bitset可以提速。

1462.课程表 IV

题目描述：

你总共需要上 numCourses 门课，课程编号依次为 0 到 numCourses-1 。你会得到一个数组 prerequisite ，其中 prerequisites[i] = [ai, bi] 表示如果你想选 bi 课程，你 必须 先选 ai 课程。

  • 有的课会有直接的先修课程，比如如果想上课程 1 ，你必须先上课程 0 ，那么会以 [0,1] 数对的形式给出先修课程数对。

先决条件也可以是 间接 的。如果课程 a 是课程 b 的先决条件，课程 b 是课程 c 的先决条件，那么课程 a 就是课程 c 的先决条件。

你也得到一个数组 queries ，其中 queries[j] = [uj, vj]。对于第 j 个查询，您应该回答课程 uj 是否是课程 vj 的先决条件。

返回一个布尔数组 answer ，其中 answer[j] 是第 j 个查询的答案。

数据范围：

$2\le numCourses \le 100,1\le q.len \le 10^4$

题解：

可以使用 $floyd$ 算法，枚举中间点，枚举起点终点，得到可达信息。

也可以直接使用bitset，使用bitset表示节点的前序节点。然后使用双重循环，更新每个节点的前序。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>> &prerequisites, vector<vector<int>> &queries)
    {
        vector<vector<int>> g(numCourses, vector<int>(numCourses, false));
        for (auto &edge : prerequisites)
        {
            int u = edge[0], v = edge[1];
            g[u][v] = true;
        }
        for (int k = 0; k < numCourses; ++k)
        {
            for (int i = 0; i < numCourses; ++i)
            {
                for (int j = 0; j < numCourses; ++j)
                {
                    g[i][j] |= g[i][k] && g[k][j];
                }
            }
        }
        vector<bool> ret;
        for (auto edge : queries)
        {
            int u = edge[0], v = edge[1];
            if (g[u][v])
                ret.emplace_back(true);
            else
                ret.emplace_back(false);
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>> &prerequisites, vector<vector<int>> &queries)
    {
        vector<vector<int>> g(numCourses);
        vector<vector<bool>> f(numCourses, vector<bool>(numCourses, false));
        vector<int> indeg(numCourses, 0);
        for (auto &edge : prerequisites)
        {
            int u = edge[0], v = edge[1];
            f[u][v] = true;
            g[u].emplace_back(v);
            indeg[v]++;
        }
        queue<int> q;
        for (int i = 0; i < numCourses; ++i)
            if (indeg[i] == 0)
                q.push(i);
        while (q.size())
        {
            auto u = q.front();
            cout << u << endl;
            q.pop();
            for (auto &v : g[u])
            {
                f[u][v] = true;
                indeg[v]--;
                if (indeg[v] == 0)
                {
                    q.push(v);
                }
                for (int i = 0; i < numCourses; ++i)
                {
                    if (f[i][u])
                    {
                        f[i][v] = true;
                    }
                }
            }
            
        }
        vector<bool> ret;
        for (auto edge : queries)
        {
            int u = edge[0], v = edge[1];
            if (f[u][v])
                ret.emplace_back(true);
            else
                ret.emplace_back(false);
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
  vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
    bitset<101> pre[numCourses];
    for (auto& edge : prerequisites) {
      int a = edge[0];
      int b = edge[1];
      pre[a][b] = 1;
    }
    for (int k = 0; k < numCourses; ++k) {
      for (int i = 0; i < numCourses; ++i) {
        if (pre[i][k]) {
          pre[i] |= pre[k];
        }
      }
    }

    int m = queries.size();
    vector<bool> res(m);
    for (int i = 0; i < m; ++i) {
      int u = queries[i][0];
      int v = queries[i][1];
      res[i] = pre[u][v];
    }
    return res;
  }
};