1
00:00:01,170 --> 00:00:03,060
Hi, everyone, welcome to this new video.

2
00:00:03,090 --> 00:00:09,300
So in this video, we are going to discuss about this collision course schedule, so suppose there are

3
00:00:09,300 --> 00:00:14,430
five courses labeled from zero and minus one that is labeled from zero to four.

4
00:00:15,420 --> 00:00:15,830
Right.

5
00:00:16,140 --> 00:00:19,150
So labeled from zero to number of courses, minus one.

6
00:00:19,470 --> 00:00:23,860
So if the number of courses are five, then they are labeled from zero to four.

7
00:00:24,720 --> 00:00:27,570
Now, what we need to do, we need to finish all the courses.

8
00:00:27,570 --> 00:00:30,990
We need to enrol in these courses and we need to finish all the courses.

9
00:00:30,990 --> 00:00:33,720
But we have some prerequisite, right.

10
00:00:33,960 --> 00:00:35,390
What do I mean by requisite?

11
00:00:35,670 --> 00:00:40,170
So before completing course when you need to complete course for.

12
00:00:40,560 --> 00:00:42,110
So this is a prerequisite.

13
00:00:42,360 --> 00:00:45,750
Similarly, before completing close to you need to complete four.

14
00:00:45,900 --> 00:00:51,840
Similarly, before completing all three, you need to complete kozulin before completing, let's say

15
00:00:51,840 --> 00:00:52,740
Ghostery.

16
00:00:52,740 --> 00:00:55,990
You also need to complete course to right.

17
00:00:56,180 --> 00:00:58,770
So this is basically when the requisite three.

18
00:00:59,370 --> 00:01:04,680
So this is the requisite error rate and what we need to do.

19
00:01:04,980 --> 00:01:09,390
So we need to tell whether we will be able to finish all these courses or not.

20
00:01:09,840 --> 00:01:10,180
Right.

21
00:01:10,200 --> 00:01:18,540
So let me try to explain again, given the number of courses, I have five courses starting from zero

22
00:01:18,540 --> 00:01:18,980
to four.

23
00:01:19,410 --> 00:01:19,790
Right.

24
00:01:20,220 --> 00:01:22,020
So some courses are independent.

25
00:01:22,020 --> 00:01:28,200
They can be enrolled in finished independently, but some courses has dependency, for example, courses

26
00:01:28,200 --> 00:01:31,830
and has a dependency on course for that before the year to complete course.

27
00:01:31,830 --> 00:01:33,720
For then only you can complete course.

28
00:01:33,720 --> 00:01:39,720
One similarly goes to has a dependency on goals for that course for must be enrolled and completed then

29
00:01:39,720 --> 00:01:41,280
only you can enroll in college to.

30
00:01:41,820 --> 00:01:44,120
Similarly, Ghostery has a dependency on course.

31
00:01:44,130 --> 00:01:46,880
One corsetry has also a dependency on Gosta.

32
00:01:47,040 --> 00:01:51,390
So this is one to course.

33
00:01:51,390 --> 00:01:57,420
One has a dependency on goals for goals too.

34
00:01:57,930 --> 00:02:01,310
Has also dependency on goals for goals.

35
00:02:01,590 --> 00:02:03,630
Three has a dependency on goals.

36
00:02:03,630 --> 00:02:08,580
One Similarly, Corsetry has a dependency on course to also.

37
00:02:09,780 --> 00:02:15,180
Right, we need to tell whether we will be able to finish all the courses or not, if we are able to

38
00:02:15,180 --> 00:02:16,920
finish all the courses, we will return, true.

39
00:02:16,920 --> 00:02:18,120
Else we will return false.

40
00:02:18,480 --> 00:02:21,550
So for this example, can we finish all the courses?

41
00:02:21,570 --> 00:02:21,990
Yes.

42
00:02:22,620 --> 00:02:22,940
True.

43
00:02:23,820 --> 00:02:26,400
So in what order will be able to finish the courses?

44
00:02:26,550 --> 00:02:32,510
First of all, I will complete course for now after completing goals for I can complete course one and

45
00:02:32,520 --> 00:02:33,450
goals to do.

46
00:02:33,450 --> 00:02:40,950
I can complete course one and two and corsetry after completing one and two, we can complete corsetry

47
00:02:41,190 --> 00:02:43,200
and courses zero is independent.

48
00:02:43,200 --> 00:02:43,610
Right.

49
00:02:44,850 --> 00:02:48,990
We started from zero to four so close to zero is independent.

50
00:02:49,080 --> 00:02:51,770
So courses zero can be completed at any time.

51
00:02:51,780 --> 00:02:57,660
Let's say I am completing courses at and or you can compute courses you do at the beginning or in between.

52
00:02:57,660 --> 00:03:01,560
Right to consider is independent so it can be enrolled and completed any time.

53
00:03:01,860 --> 00:03:04,740
So in this case, for this example, I am going to return.

54
00:03:04,740 --> 00:03:07,770
True that I will be able to finish all the courses.

55
00:03:09,200 --> 00:03:11,460
Right, so let's take another example.

56
00:03:12,950 --> 00:03:13,760
So here.

57
00:03:14,970 --> 00:03:17,170
They have provided this example, right?

58
00:03:17,190 --> 00:03:27,150
So let's talk about this, so I have two courses, goals zero and goals one and goals one has a dependency

59
00:03:27,150 --> 00:03:27,990
on goals zero.

60
00:03:27,990 --> 00:03:31,190
So goals one has a dependency on goal zero.

61
00:03:31,350 --> 00:03:32,950
So can I finish all the courses?

62
00:03:33,270 --> 00:03:33,720
Yes.

63
00:03:33,990 --> 00:03:35,970
First of all, I will finish goals zero.

64
00:03:36,120 --> 00:03:39,800
After finishing courses zero, I can Andolan finish goals one.

65
00:03:40,290 --> 00:03:43,490
So yes, through I can finish all the courses.

66
00:03:43,500 --> 00:03:44,950
So that's why the output is true.

67
00:03:45,750 --> 00:03:47,010
Let's talk about this case.

68
00:03:47,520 --> 00:03:50,640
The number of course, is two goals zero and goals one.

69
00:03:51,300 --> 00:03:54,600
So goals one has a dependency on goal zero goals.

70
00:03:54,600 --> 00:03:57,130
One has a dependency on goals.

71
00:03:57,150 --> 00:04:04,020
Zero net first unit to enroll and complete courses zero course zero has a dependency on goals one.

72
00:04:04,260 --> 00:04:11,120
So Goals Zero has a dependency on goals, one that means you need to first complete goals.

73
00:04:11,140 --> 00:04:13,010
One, then you can complete course zero.

74
00:04:13,140 --> 00:04:15,480
So this is basically false, right?

75
00:04:15,630 --> 00:04:23,640
We cannot complete we will not be able to finish the course because there is a cycle right courses releasing

76
00:04:23,850 --> 00:04:27,780
first complete goals and then you can complete me course of anything.

77
00:04:27,780 --> 00:04:30,540
First, complete goals is zero, then you can complete me.

78
00:04:31,110 --> 00:04:32,430
So what do we have?

79
00:04:32,640 --> 00:04:34,380
We have one cycle here.

80
00:04:34,890 --> 00:04:40,410
Since we have a cycle, that means we will not be able to finish all the courses.

81
00:04:40,410 --> 00:04:42,300
So that's why the output is false.

82
00:04:42,990 --> 00:04:47,610
So I hope you have understood the question right now how we can solve this question.

83
00:04:48,120 --> 00:04:50,160
So it's very simple, very, very simple.

84
00:04:50,160 --> 00:04:54,150
But you need to do year to first figure out the A graph.

85
00:04:54,150 --> 00:05:02,180
Like what I am saying is let's these are these are your dependencies to the Pentagon for that.

86
00:05:02,220 --> 00:05:03,420
It three depends on too.

87
00:05:04,050 --> 00:05:05,580
So what it will look like.

88
00:05:05,580 --> 00:05:06,870
I have one and two.

89
00:05:07,410 --> 00:05:13,620
So when the goes for two also depends on cause for right.

90
00:05:14,130 --> 00:05:20,700
Two is depending upon goals for three years, depending upon two to three is depending upon two.

91
00:05:20,880 --> 00:05:23,790
So tell me whether can I finish all the courses or not.

92
00:05:23,790 --> 00:05:25,500
Yes, I can finish all the courses.

93
00:05:25,500 --> 00:05:26,060
So true.

94
00:05:26,550 --> 00:05:29,660
Now let's say I have one more prerequisite, three and four.

95
00:05:29,850 --> 00:05:31,640
So three depends upon goals.

96
00:05:31,650 --> 00:05:33,750
Four to three depends.

97
00:05:33,750 --> 00:05:34,140
No, no.

98
00:05:34,140 --> 00:05:35,130
Let's do the opposite.

99
00:05:36,920 --> 00:05:45,440
For depends upon Ghostery, right, for depends upon corsetry, so for depends upon corsetry, this

100
00:05:45,440 --> 00:05:53,090
is a late word for the thing for saying you can complete me only when you can complete corsetry.

101
00:05:54,530 --> 00:06:02,870
So for is saying you can complete me only when you have completed corsetry corsetry saying you can complete

102
00:06:02,870 --> 00:06:09,080
me only when you have completed coast to coast do you think you can complete me only when you have completed

103
00:06:09,080 --> 00:06:09,710
goals for.

104
00:06:10,220 --> 00:06:11,600
So this is when cycle.

105
00:06:11,600 --> 00:06:11,990
Right.

106
00:06:12,410 --> 00:06:13,760
This is one cycle.

107
00:06:13,760 --> 00:06:15,940
So I will not be able to finish all the courses.

108
00:06:15,950 --> 00:06:17,630
So that's why the output will be false.

109
00:06:20,310 --> 00:06:21,870
So how are we going to solve this problem?

110
00:06:21,900 --> 00:06:22,770
It's very simple.

111
00:06:22,770 --> 00:06:24,610
There are two ways of solving the problem.

112
00:06:25,710 --> 00:06:32,080
So first, we basically cycle detection rate, first rate cycle detection.

113
00:06:32,100 --> 00:06:35,970
So given the speed accusatory, we are provided with this prerequisite.

114
00:06:35,970 --> 00:06:39,360
At any rate, what we will do, we will construct the graph.

115
00:06:40,770 --> 00:06:41,970
We will make this graph.

116
00:06:41,970 --> 00:06:46,140
And then in this graph I will run one cycle detection algorithm.

117
00:06:46,950 --> 00:06:48,610
So if the cycle is present.

118
00:06:48,840 --> 00:06:49,560
So if.

119
00:06:51,930 --> 00:06:59,550
Is present then, in that case, false, you cannot finish all the courses if cycle not present, if

120
00:06:59,730 --> 00:07:04,590
no cycle, that means you will be able to finish all the courses.

121
00:07:04,800 --> 00:07:06,720
So in that case, your answer will be true.

122
00:07:07,650 --> 00:07:15,090
So after making this graph, we can run, we can write the code for cycle detection algorithm so cyclodextrin

123
00:07:15,090 --> 00:07:19,910
algorithm can be implemented using the algorithm so we can write the code for cycle detection.

124
00:07:20,310 --> 00:07:26,460
And if the cycle is present false, if no cycle, then true, I will be able to finish all the courses.

125
00:07:27,360 --> 00:07:31,560
The second way of solving this problem is basically with the help of Topological Saad.

126
00:07:33,550 --> 00:07:34,990
Right, topological.

127
00:07:36,430 --> 00:07:42,970
So in topological start, if you remember, I told you that we will get an order, we will get an order

128
00:07:42,970 --> 00:07:49,530
in which we need to finish because the topological sword is used in DAG directed acyclic graph.

129
00:07:49,960 --> 00:07:50,330
Right.

130
00:07:50,680 --> 00:07:52,540
So what do we do in logical thought?

131
00:07:52,540 --> 00:07:58,420
We used to get one order in which we need to visit all the elements so topological so it can be used

132
00:07:58,420 --> 00:07:58,740
here.

133
00:07:59,620 --> 00:07:59,920
Right?

134
00:08:00,130 --> 00:08:04,530
So either you can write the code for cycle detection or you can use topological sword.

135
00:08:04,540 --> 00:08:05,800
Both of them will work.

136
00:08:07,720 --> 00:08:08,090
Right.

137
00:08:09,130 --> 00:08:16,150
So in topological sort, if I'm able to visit all the elements, if I am able to visit all the courses,

138
00:08:16,390 --> 00:08:22,180
if I'm able to enrol in all the courses and finish them, then I will return to otherwise I will return

139
00:08:22,180 --> 00:08:22,570
false.

140
00:08:22,810 --> 00:08:28,210
If I'm not able to visit all the elements, all the courses, then I will return false.

141
00:08:29,320 --> 00:08:31,240
So you can write the code for any one of them.

142
00:08:31,250 --> 00:08:31,600
Right.

143
00:08:32,020 --> 00:08:37,630
So what we will be doing, we will be writing the code for topological sort in our next video.

144
00:08:38,860 --> 00:08:40,809
So this is all about this device.

145
00:08:41,140 --> 00:08:42,549
I will see you in the next one.

146
00:08:42,700 --> 00:08:47,170
And I highly recommend that you try to implement either one of them, either try to implement cyclic

147
00:08:47,200 --> 00:08:52,310
reduction using DFS or try to write the code for topological right.

148
00:08:52,600 --> 00:08:54,520
So this is all about this video.

149
00:08:54,550 --> 00:08:55,760
I will see you in the next one.

150
00:08:55,780 --> 00:08:56,350
Thank you.