leetcode

0 // DFS

1 class Solution {

2 public:

3 vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>> &prerequisites,

4 vector<vector<int>> &queries) {

5 vector<vector<int>> adj(numCourses);

6 vector<unordered_set<int>> pre(numCourses);

7

8 for (auto &p : prerequisites)

9 adj[p[0]].push_back(p[1]);

10

11 for (int i = 0; i < numCourses; i++) {

12 unordered_set<int> visited;

13 stack<int> st;

14 st.push(i);

15 visited.insert(i);

16 while (!st.empty()) {

17 int crnt = st.top();

18 st.pop();

19 for (int &c : adj[crnt]) {

20 if (visited.count(c)) continue;

21 visited.insert(c);

22 pre[c].insert(i);

23 st.push(c);

24 }

25 }

26 }

27

28 vector<bool> res;

29 for (auto &p : queries)

30 res.push_back(pre[p[1]].count(p[0]));

31 return res;

32 }

33 };

34

35 // Topological sort with dependency propagation

36 class Solution {

37 public:

38 vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>> &prerequisites,

39 vector<vector<int>> &queries) {

40 vector<unordered_set<int>> pre(numCourses);

41 vector<vector<int>> adj(numCourses);

42 vector<int> count(numCourses);

43

44 for (auto &p : prerequisites) {

45 adj[p[0]].push_back(p[1]);

46 count[p[1]]++;

47 }

48

49 queue<int> q;

50 for (int i = 0; i < numCourses; i++)

51 if (!count[i]) q.push(i);

52

53 while (!q.empty()) {

54 int crnt = q.front();

55 q.pop();

56 for (int &c : adj[crnt]) {

57 pre[c].insert(crnt);

58 pre[c].insert(pre[crnt].begin(), pre[crnt].end());

59 if (!--count[c]) q.push(c);

60 }

61 }

62

63 vector<bool> res;

64 for (auto &p : queries)

65 res.push_back(pre[p[1]].count(p[0]));

66 return res;

67 }

68 };

69

70 // Topological sort using bitseclass Solution {

71 public:

72 vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>> &prerequisites,

73 vector<vector<int>> &queries) {

74 vector<bitset<100>> pre(numCourses);

75 vector<vector<int>> adj(numCourses);

76 vector<int> count(numCourses);

77

78 for (auto &p : prerequisites) {

79 adj[p[0]].push_back(p[1]);

80 count[p[1]]++;

81 }

82

83 queue<int> q;

84 for (int i = 0; i < numCourses; i++)

85 if (!count[i]) q.push(i);

86

87 while (!q.empty()) {

88 int crnt = q.front();

89 q.pop();

90 for (int &c : adj[crnt]) {

91 pre[c].set(crnt);

92 pre[c] |= pre[crnt];

93 if (!--count[c]) q.push(c);

94 }

95 }

96

97 vector<bool> res;

98 for (auto &p : queries)

99 res.push_back(pre[p[1]][p[0]]);

100 return res;

101 }

102 }

103 ;