1
00:00:00,460 --> 00:00:01,510
Welcome back.

2
00:00:01,510 --> 00:00:05,650
Let's now go ahead and code the solution that we discussed in the previous video.

3
00:00:05,650 --> 00:00:07,780
Now for this we will write a function.

4
00:00:07,780 --> 00:00:09,940
Let's call it count components.

5
00:00:11,720 --> 00:00:17,210
And this function is going to take in n, which is the number of vertices and the edges array.

6
00:00:17,690 --> 00:00:19,820
Now once we are inside this function.

7
00:00:20,790 --> 00:00:23,100
We will first build the adjacency list.

8
00:00:23,100 --> 00:00:30,270
So let's say const graph is equal to build adjacency list which is a helper function that we will write

9
00:00:30,270 --> 00:00:30,510
right.

10
00:00:30,510 --> 00:00:32,490
So build adjacency list.

11
00:00:32,490 --> 00:00:35,850
And then over here we will also pass n and the edges to it.

12
00:00:35,970 --> 00:00:40,650
Now let's just go ahead and write this helper function before we proceed with the main function over

13
00:00:40,650 --> 00:00:41,040
here.

14
00:00:41,040 --> 00:00:46,260
So over here we can say const and the function is build adjacency list.

15
00:00:46,290 --> 00:00:49,440
Now this function also takes in n and the edges.

16
00:00:50,810 --> 00:00:51,230
All right.

17
00:00:51,230 --> 00:00:55,280
Now inside this function let's say const adjacency list.

18
00:00:55,400 --> 00:00:59,870
And let's just make an empty array, an array of arrays.

19
00:00:59,870 --> 00:01:01,340
It's going to be an array of arrays.

20
00:01:01,340 --> 00:01:03,860
And each element is going to be an empty array.

21
00:01:03,860 --> 00:01:04,160
All right.

22
00:01:04,160 --> 00:01:07,130
So and the count of the empty arrays is going to be n.

23
00:01:07,130 --> 00:01:09,080
So we're going to have an array of arrays.

24
00:01:09,080 --> 00:01:10,970
So let me just show that over here.

25
00:01:10,970 --> 00:01:12,740
So this is going to be an array.

26
00:01:13,190 --> 00:01:15,590
And each element is going to be an empty array.

27
00:01:15,740 --> 00:01:16,160
Right.

28
00:01:16,160 --> 00:01:17,390
So something like this.

29
00:01:17,390 --> 00:01:23,180
And the number of empty arrays that we have inside this array is going to be equal to n which is the

30
00:01:23,180 --> 00:01:24,200
number of vertices.

31
00:01:24,200 --> 00:01:25,820
So this is what we're doing over here.

32
00:01:25,820 --> 00:01:28,310
So let's go ahead and we say new array.

33
00:01:30,200 --> 00:01:32,150
And the size is going to be n.

34
00:01:32,940 --> 00:01:35,670
Then we say dot fill with zero.

35
00:01:36,270 --> 00:01:38,160
And then we use the dot map operator.

36
00:01:38,160 --> 00:01:39,240
So dot map.

37
00:01:42,140 --> 00:01:42,680
All right.

38
00:01:42,680 --> 00:01:47,270
So this will give us an array which is which is like this.

39
00:01:47,270 --> 00:01:49,760
And then it will have empty arrays inside it.

40
00:01:49,760 --> 00:01:49,940
Right.

41
00:01:49,940 --> 00:01:51,560
So these are going to be the elements.

42
00:01:51,560 --> 00:01:55,370
So for each of these n elements we're just iterating through the array.

43
00:01:55,370 --> 00:01:57,170
And we are changing it to an empty array.

44
00:01:57,170 --> 00:01:59,060
So this is what we get after this.

45
00:01:59,060 --> 00:01:59,300
Right.

46
00:01:59,300 --> 00:02:02,990
So adjacencylist is just an array of empty arrays at this point.

47
00:02:02,990 --> 00:02:07,430
Now we will just iterate through the edges array which we have passed in over here.

48
00:02:07,430 --> 00:02:09,110
So let's say for.

49
00:02:09,900 --> 00:02:10,530
Let.

50
00:02:10,530 --> 00:02:12,240
Edge of edges.

51
00:02:14,170 --> 00:02:18,190
So we take each value in the edges array which is again an array.

52
00:02:18,190 --> 00:02:18,550
Right.

53
00:02:18,550 --> 00:02:20,110
So we have this for loop.

54
00:02:20,110 --> 00:02:24,760
And then let's just find the first and second element in each of those arrays.

55
00:02:24,760 --> 00:02:24,970
Right.

56
00:02:24,970 --> 00:02:29,020
So the edge will have two nodes u and v as mentioned in the question.

57
00:02:29,020 --> 00:02:35,110
So let's say let node one is equal to edge at index zero.

58
00:02:36,760 --> 00:02:42,130
And let node two is equal to h at index one.

59
00:02:42,850 --> 00:02:43,150
All right.

60
00:02:43,150 --> 00:02:44,770
So this is just like u and v.

61
00:02:44,770 --> 00:02:45,940
So this is u.

62
00:02:45,940 --> 00:02:47,830
This is v as mentioned in the question.

63
00:02:47,830 --> 00:02:49,930
So there is a edge between u and v.

64
00:02:49,930 --> 00:02:52,450
So we identify these two vertices.

65
00:02:52,480 --> 00:02:57,940
Now we are just going to push the respective edge into the correct position in the adjacency list.

66
00:02:57,940 --> 00:03:02,680
So in the adjacency list which at this point is empty at node one.

67
00:03:03,390 --> 00:03:06,210
We are going to push node two right.

68
00:03:06,210 --> 00:03:09,030
So dot push and we're just passing node two.

69
00:03:09,030 --> 00:03:12,000
And we're going to do the same thing at node two also.

70
00:03:12,000 --> 00:03:16,590
So adjacency list at node two we will just push node one.

71
00:03:18,730 --> 00:03:22,480
Now we are doing this because over here this graph is undirected.

72
00:03:22,480 --> 00:03:24,280
So the edge goes both ways.

73
00:03:24,280 --> 00:03:25,540
So that's why we are doing this.

74
00:03:25,540 --> 00:03:27,430
And then we have built the adjacency list.

75
00:03:27,430 --> 00:03:28,870
Now let's just return this.

76
00:03:28,870 --> 00:03:31,210
So return adjacency list.

77
00:03:31,630 --> 00:03:32,170
All right.

78
00:03:32,170 --> 00:03:35,410
So again this is our helper function to build the adjacency list.

79
00:03:35,410 --> 00:03:38,620
So we are back at the count components function.

80
00:03:38,620 --> 00:03:44,230
And over here we have built the adjacency list from the edges and the number of vertices.

81
00:03:44,230 --> 00:03:46,180
Now what we will do is.

82
00:03:46,740 --> 00:03:48,840
We will have a visited object.

83
00:03:48,840 --> 00:03:54,420
So let's say const visited to track whether a vertex is visited or not.

84
00:03:54,420 --> 00:03:58,170
And initially it's going to be an empty object and then we will have a count.

85
00:03:58,170 --> 00:04:00,630
So this count is going to be the number of components.

86
00:04:00,630 --> 00:04:03,690
So we will just go through the graph which is given to us.

87
00:04:03,690 --> 00:04:05,820
And finally we will return this count.

88
00:04:06,210 --> 00:04:06,600
All right.

89
00:04:06,600 --> 00:04:08,190
So this is what we're going to do.

90
00:04:08,190 --> 00:04:08,670
Now.

91
00:04:08,670 --> 00:04:11,280
What we will do is we will just loop through the vertices.

92
00:04:11,280 --> 00:04:15,810
And then if the particular vertex is not visited we will increment count.

93
00:04:15,810 --> 00:04:19,440
And we will call the depth first search function which again will go ahead.

94
00:04:19,440 --> 00:04:24,570
And right now we will call that to traverse the nodes which are connected to that particular node.

95
00:04:24,570 --> 00:04:25,740
So let's go ahead and write this.

96
00:04:25,740 --> 00:04:27,540
So for let vertex.

97
00:04:28,470 --> 00:04:35,730
Is equal to zero and vertex less than n, because there are n vertices, and it's going to be zero if

98
00:04:35,730 --> 00:04:36,810
there are five vertices.

99
00:04:36,840 --> 00:04:39,390
The vertices are going to be zero, one, two, three, four, right.

100
00:04:39,390 --> 00:04:45,750
So for a vertex zero till vertex less than n and then we are just going to say vertex plus plus.

101
00:04:47,470 --> 00:04:47,950
All right.

102
00:04:47,980 --> 00:04:54,640
Now inside this we are going to check if that particular vertex is there in our visited object or not.

103
00:04:54,640 --> 00:04:56,650
So if not.

104
00:04:58,590 --> 00:05:00,780
Visited at vertex.

105
00:05:01,500 --> 00:05:07,980
If it's not visited then we will call the depth first search DFS function right, the depth depth first

106
00:05:07,980 --> 00:05:11,850
search function on that particular vertex, and then we will increment our count.

107
00:05:11,850 --> 00:05:13,140
So we say count plus plus.

108
00:05:13,140 --> 00:05:14,910
So we have identified a new component.

109
00:05:14,910 --> 00:05:16,500
So that's why we are incrementing the count.

110
00:05:16,500 --> 00:05:18,390
And then we are going to write a DFS function.

111
00:05:18,390 --> 00:05:23,250
So we will call that function that helper function to traverse all the nodes which are connected to

112
00:05:23,250 --> 00:05:24,450
that particular vertex.

113
00:05:24,450 --> 00:05:27,390
So we will pass in the graph to this DFS function.

114
00:05:27,390 --> 00:05:29,340
And then we will pass in the vertex.

115
00:05:29,340 --> 00:05:29,940
All right.

116
00:05:29,940 --> 00:05:33,150
And we will also pass in the visited object.

117
00:05:36,460 --> 00:05:37,450
All right, so that's it.

118
00:05:37,450 --> 00:05:40,540
Now we just have to write our DFS helper function.

119
00:05:40,540 --> 00:05:42,220
So let's go ahead and write that over here.

120
00:05:42,220 --> 00:05:45,040
So we can say const DFS.

121
00:05:48,580 --> 00:05:52,210
And this function is going to take in the graph.

122
00:05:52,600 --> 00:05:58,150
And it will take in a particular vertex and it will take in the visited object.

123
00:05:59,050 --> 00:05:59,320
All right.

124
00:05:59,320 --> 00:06:03,670
So this is just a straightforward depth first search which you've already discussed.

125
00:06:03,670 --> 00:06:08,260
So initially we say that visited at the particular vertex we mark it as true.

126
00:06:10,220 --> 00:06:10,670
All right.

127
00:06:10,700 --> 00:06:14,930
Now we're just going to find the neighbors of that particular vertex.

128
00:06:14,930 --> 00:06:18,710
And for this we will use the adjacency list which we are passing to this function.

129
00:06:18,710 --> 00:06:21,620
So const neighbors is equal to graph.

130
00:06:22,330 --> 00:06:23,590
At vertex.

131
00:06:24,940 --> 00:06:27,670
And over here this graph is the adjacency list which you are passing.

132
00:06:27,670 --> 00:06:27,970
Right.

133
00:06:27,970 --> 00:06:29,680
So graph is the adjacency list.

134
00:06:29,680 --> 00:06:31,000
And we are passing it over here.

135
00:06:31,000 --> 00:06:33,970
So over here we are getting the adjacency list.

136
00:06:33,970 --> 00:06:36,970
And we are going to that particular key value or.

137
00:06:36,970 --> 00:06:37,300
All right.

138
00:06:37,300 --> 00:06:39,520
So in that again this is an array.

139
00:06:39,520 --> 00:06:41,830
So we are going to that particular index in the array.

140
00:06:41,830 --> 00:06:43,900
And then we are getting back an array.

141
00:06:43,900 --> 00:06:44,290
Right.

142
00:06:44,290 --> 00:06:46,060
We have seen that this is an array of arrays.

143
00:06:46,060 --> 00:06:51,760
So neighbors now will be an array which represents the uh neighbors of that particular vertex.

144
00:06:51,790 --> 00:06:53,470
Now we have the neighbors.

145
00:06:53,470 --> 00:06:56,200
Now we are just going to loop through the neighbors.

146
00:06:56,200 --> 00:07:01,720
And if we see that any of the neighbors is not visited, then we are just going to call recursively

147
00:07:01,720 --> 00:07:04,270
the DFS function on that particular vertex.

148
00:07:04,270 --> 00:07:05,470
So let's go ahead and do that.

149
00:07:05,470 --> 00:07:06,700
So for let.

150
00:07:07,590 --> 00:07:13,080
I is equal to zero I less than neighbors dot length.

151
00:07:14,970 --> 00:07:16,260
I plus plus.

152
00:07:17,010 --> 00:07:23,310
Now inside this we are going to check the neighbor whether that particular neighbor is visited or not.

153
00:07:23,310 --> 00:07:30,540
So just to make our code neat, let's have const neighbor over here, which is equal to neighbors at

154
00:07:30,540 --> 00:07:30,930
I.

155
00:07:31,050 --> 00:07:33,480
So this is a particular neighbor.

156
00:07:33,480 --> 00:07:33,960
All right.

157
00:07:33,990 --> 00:07:35,910
Now we are going to check if this is visited.

158
00:07:35,910 --> 00:07:39,480
So if not visited at neighbor.

159
00:07:39,720 --> 00:07:46,650
So if that particular vertex is not yet visited then we will call DFS recursively on that vertex.

160
00:07:46,650 --> 00:07:46,980
Right.

161
00:07:46,980 --> 00:07:49,680
So DFS again we are passing the graph.

162
00:07:49,680 --> 00:07:54,510
We are passing that particular neighbor and we are passing the visited object.

163
00:07:55,320 --> 00:07:55,890
That's it.

164
00:07:55,890 --> 00:07:59,310
So this is our depth first search uh helper function.

165
00:07:59,310 --> 00:07:59,700
Right.

166
00:07:59,700 --> 00:08:05,370
So once we are out of this we will have visited all the neighbors of that particular vertex.

167
00:08:05,370 --> 00:08:05,730
Right.

168
00:08:05,730 --> 00:08:09,180
So again this is how we are identifying the components.

169
00:08:09,180 --> 00:08:14,820
So when we call the DFS function all the vertices which are connected to it or which are part of that

170
00:08:14,820 --> 00:08:16,830
particular component will be visited.

171
00:08:16,830 --> 00:08:22,500
So we will again call DFS only when we see a vertex which is not yet visited.

172
00:08:22,500 --> 00:08:24,330
So that is what we are doing over here.

173
00:08:24,330 --> 00:08:24,780
All right.

174
00:08:24,780 --> 00:08:25,950
So this is our code.

175
00:08:25,950 --> 00:08:27,300
So we are done with the function.

176
00:08:27,300 --> 00:08:28,770
Now let's go ahead and test it.

177
00:08:28,770 --> 00:08:33,870
Now for this let's take an example for example let's say n n is equal to five.

178
00:08:33,870 --> 00:08:38,040
So let's say const n is equal to five.

179
00:08:38,040 --> 00:08:42,960
So we have the nodes 0123 and four.

180
00:08:42,960 --> 00:08:44,880
And then let's have an edges array.

181
00:08:44,880 --> 00:08:46,080
So const edges.

182
00:08:46,110 --> 00:08:48,480
Let's say this is an array of arrays.

183
00:08:48,480 --> 00:08:50,970
Let's say there is a link between 0 and 1.

184
00:08:50,970 --> 00:08:53,220
And let's say there is a link between.

185
00:08:53,840 --> 00:08:55,220
One and two.

186
00:08:55,950 --> 00:08:58,830
And there is a link between 2 and 3.

187
00:08:59,560 --> 00:09:02,380
And let's say there is nothing connected to four.

188
00:09:02,380 --> 00:09:05,050
So our expectation is that we should get two right?

189
00:09:05,050 --> 00:09:06,160
The answer should be two.

190
00:09:06,190 --> 00:09:08,650
So let's call our function and test it out.

191
00:09:10,760 --> 00:09:14,270
And we're going to pass in N and the edges over here.

192
00:09:15,450 --> 00:09:19,380
And let's just run our code and take a look at the output.

193
00:09:19,770 --> 00:09:20,520
All right.

194
00:09:20,520 --> 00:09:22,950
So yes, you can see we have the answer as two.

195
00:09:22,950 --> 00:09:23,250
Right.

196
00:09:23,250 --> 00:09:24,120
So this is correct.

197
00:09:24,120 --> 00:09:24,570
Why is that.

198
00:09:24,570 --> 00:09:26,640
So we have zero and one connected.

199
00:09:26,640 --> 00:09:28,350
Let me just draw this out over here.

200
00:09:28,350 --> 00:09:32,070
We'll just take a few test cases and draw it out over here so that we are very thorough.

201
00:09:32,070 --> 00:09:37,020
And then we will take a sample input and walk through the code to understand what's happening in greater

202
00:09:37,020 --> 00:09:37,500
depth.

203
00:09:38,460 --> 00:09:38,910
All right.

204
00:09:38,910 --> 00:09:40,200
So let's take a look.

205
00:09:40,200 --> 00:09:42,360
So there is a link between 0 and 1.

206
00:09:42,900 --> 00:09:45,240
And there is a link between 1 and 2.

207
00:09:45,240 --> 00:09:47,520
And there is a link between 2 and 3.

208
00:09:47,520 --> 00:09:49,980
And then we have n equal to five.

209
00:09:49,980 --> 00:09:51,360
So these are our vertices.

210
00:09:51,360 --> 00:09:54,000
So there is no link between four and anything.

211
00:09:54,000 --> 00:09:55,860
So this is how our graph looks like.

212
00:09:55,860 --> 00:09:57,930
So we can see clearly there are two components.

213
00:09:57,930 --> 00:10:00,540
So this is one component and this is the second component.

214
00:10:00,540 --> 00:10:02,820
That's why we have our answer two over here.

215
00:10:02,820 --> 00:10:04,440
Now let's take another example.

216
00:10:04,440 --> 00:10:07,680
So let's just delete this and let's take another example.

217
00:10:08,070 --> 00:10:12,270
So for example I say there is a connection between 0 and 1 one and two.

218
00:10:12,270 --> 00:10:16,380
And let's say there is a connection between 3 and 4.

219
00:10:20,870 --> 00:10:21,590
All right.

220
00:10:21,770 --> 00:10:24,290
So again and then let's increment n.

221
00:10:24,290 --> 00:10:26,090
So let's make n is equal to seven.

222
00:10:26,090 --> 00:10:27,740
So I'm just changing the example.

223
00:10:27,740 --> 00:10:30,050
So we have values till six.

224
00:10:30,050 --> 00:10:31,160
So 0 to 6.

225
00:10:31,160 --> 00:10:32,540
These are our nodes.

226
00:10:32,570 --> 00:10:37,490
Now let's say there is also a connection between 5 and 6.

227
00:10:38,740 --> 00:10:41,440
All right, now let's go ahead and run our code.

228
00:10:44,470 --> 00:10:46,420
And you can see we have three components.

229
00:10:46,420 --> 00:10:47,980
Let's try to draw this out.

230
00:10:48,340 --> 00:10:51,430
So we have a connection between 0 and 1.

231
00:10:51,430 --> 00:10:53,890
There is a connection between 1 and 2.

232
00:10:53,920 --> 00:10:56,590
There is a connection between 3 and 4.

233
00:10:57,040 --> 00:10:59,620
And there is a connection between 5 and 6.

234
00:10:59,620 --> 00:11:00,430
So yes.

235
00:11:00,430 --> 00:11:01,810
So this is component one.

236
00:11:01,810 --> 00:11:04,000
This is component two and this is component three.

237
00:11:04,000 --> 00:11:04,360
All right.

238
00:11:04,360 --> 00:11:05,710
So yes three is correct.

239
00:11:05,710 --> 00:11:07,510
Now let's take this example.

240
00:11:07,510 --> 00:11:10,240
And let's just walk through the code and see what's happening.

241
00:11:12,170 --> 00:11:17,900
So we call the count components function and we are passing n is equal to seven.

242
00:11:17,900 --> 00:11:20,060
And we are passing this edges array over here.

243
00:11:20,090 --> 00:11:20,330
All right.

244
00:11:20,330 --> 00:11:21,530
So these connections.

245
00:11:21,530 --> 00:11:26,150
So once we are inside the function over here first we are building the adjacency list.

246
00:11:26,150 --> 00:11:28,850
So we come to the build adjacency list over here.

247
00:11:28,850 --> 00:11:29,150
All right.

248
00:11:29,150 --> 00:11:30,680
So let's see what's happening over here.

249
00:11:31,010 --> 00:11:31,970
Let's just draw it.

250
00:11:31,970 --> 00:11:36,140
So in this part of the code we are having an array of empty arrays.

251
00:11:36,140 --> 00:11:40,310
And over here this will have elements equal to n and n is equal to seven.

252
00:11:40,310 --> 00:11:41,900
So this is going to look like this right.

253
00:11:41,900 --> 00:11:44,300
So we are going to have seven empty arrays.

254
00:11:45,170 --> 00:11:49,370
Let me just, uh, draw this a bit different so that it's easy to visualize.

255
00:11:49,400 --> 00:11:50,600
So we have.

256
00:11:51,090 --> 00:11:52,770
The first empty array over here.

257
00:11:52,890 --> 00:11:54,270
The second empty array over here.

258
00:11:54,300 --> 00:11:55,890
The third empty array over here.

259
00:11:56,190 --> 00:11:57,330
The fourth empty array.

260
00:11:57,360 --> 00:11:58,410
Fifth empty array.

261
00:11:58,440 --> 00:12:00,000
Sixth empty array.

262
00:12:00,000 --> 00:12:01,320
And seventh empty array.

263
00:12:01,320 --> 00:12:04,740
So this is how adjacency list is going to look at this point.

264
00:12:04,740 --> 00:12:07,770
Then we are just going to loop through the edges array right.

265
00:12:07,770 --> 00:12:10,620
So again let's take a look at our edges array.

266
00:12:11,660 --> 00:12:13,550
It's looking like this right now.

267
00:12:13,550 --> 00:12:16,970
For each of these, we are going to take this as node one and this as node two.

268
00:12:17,000 --> 00:12:18,350
So that is happening over here.

269
00:12:18,350 --> 00:12:23,180
And then we are going to push node two into node one at the adjacency list.

270
00:12:23,180 --> 00:12:24,740
So let's just do it for one example.

271
00:12:24,740 --> 00:12:26,210
So we have zero one over here.

272
00:12:26,210 --> 00:12:26,540
All right.

273
00:12:26,540 --> 00:12:28,970
So this is this link over here zero one.

274
00:12:28,970 --> 00:12:31,640
So node one let me just take a pen.

275
00:12:31,640 --> 00:12:33,110
This is going to be node one.

276
00:12:37,340 --> 00:12:38,780
This is going to be node one.

277
00:12:38,780 --> 00:12:40,250
This is going to be node two.

278
00:12:40,280 --> 00:12:42,830
So adjacency list at node one.

279
00:12:42,830 --> 00:12:44,840
So this index over here is one right.

280
00:12:44,840 --> 00:12:45,800
So this is zero.

281
00:12:45,830 --> 00:12:49,760
This is one this is two this is three this is four this is five this is six.

282
00:12:49,760 --> 00:12:50,480
The indices.

283
00:12:50,480 --> 00:12:52,730
So at one right.

284
00:12:52,730 --> 00:12:54,710
So at zero this is the index right.

285
00:12:54,710 --> 00:12:58,370
So at zero we are going to insert node two which is one.

286
00:12:58,370 --> 00:12:59,870
So over here we are going to insert one.

287
00:12:59,870 --> 00:13:03,200
So this means means there is a link between 0 and 1.

288
00:13:03,200 --> 00:13:07,970
And because this is an undirected graph we are also pushing node one at node two.

289
00:13:08,000 --> 00:13:08,990
So node two is one.

290
00:13:08,990 --> 00:13:09,830
So index one.

291
00:13:09,830 --> 00:13:12,770
And we are pushing node one which is zero right.

292
00:13:12,770 --> 00:13:14,390
So we are getting zero over here as well.

293
00:13:14,390 --> 00:13:17,240
So this is what we're doing then when we take this link.

294
00:13:17,240 --> 00:13:20,420
So at index one we are going to push two.

295
00:13:20,420 --> 00:13:22,970
And at index two we are going to push one.

296
00:13:23,450 --> 00:13:23,930
All right.

297
00:13:23,930 --> 00:13:27,260
And then when we take index three we are going to push four.

298
00:13:27,590 --> 00:13:30,050
And at index four we are going to push three.

299
00:13:30,140 --> 00:13:32,990
And at index five we are going to push six.

300
00:13:32,990 --> 00:13:35,900
And at index six we are going to push the value five.

301
00:13:35,900 --> 00:13:39,230
So this is how our adjacency list is going to look like.

302
00:13:39,350 --> 00:13:39,650
All right.

303
00:13:39,650 --> 00:13:43,910
So let me just make some space over here and clean this up a bit.

304
00:13:43,910 --> 00:13:46,310
Now we got our adjacency list.

305
00:13:47,100 --> 00:13:50,310
And we are back in our main function which is count components.

306
00:13:50,310 --> 00:13:53,670
So this graph over here is this adjacency list at this point.

307
00:13:53,670 --> 00:13:56,970
Now we have the visited object which is empty at this point.

308
00:13:56,970 --> 00:13:59,100
So let me just write that over here.

309
00:13:59,100 --> 00:14:01,170
So we have the visited object.

310
00:14:04,230 --> 00:14:05,250
And this is empty.

311
00:14:05,280 --> 00:14:05,910
All right.

312
00:14:05,940 --> 00:14:07,830
Now over here, count is equal to zero.

313
00:14:07,830 --> 00:14:11,070
So count at this point is equal to zero.

314
00:14:11,580 --> 00:14:12,810
Then we come over here.

315
00:14:12,810 --> 00:14:14,490
Now we are going to take the values.

316
00:14:14,490 --> 00:14:18,570
Vertex is going to take the values zero to less than n n is equal to seven.

317
00:14:18,570 --> 00:14:22,470
So it's going to take the values 0123456.

318
00:14:22,470 --> 00:14:22,920
Right.

319
00:14:24,800 --> 00:14:25,040
All right.

320
00:14:25,040 --> 00:14:26,120
So initially it's zero.

321
00:14:26,120 --> 00:14:29,720
Now we are checking whether the vertex zero is visited.

322
00:14:29,720 --> 00:14:31,670
We see that it's not visited right.

323
00:14:31,670 --> 00:14:33,440
So we come inside.

324
00:14:33,440 --> 00:14:34,460
We increment the count.

325
00:14:34,460 --> 00:14:35,630
So count becomes one.

326
00:14:35,630 --> 00:14:40,100
And then we are calling the DFS function where we are passing the vertex zero.

327
00:14:40,100 --> 00:14:41,120
So vertex is zero.

328
00:14:41,120 --> 00:14:42,470
Now let's see what's happening.

329
00:14:42,470 --> 00:14:44,060
We come to the DFS function.

330
00:14:44,060 --> 00:14:44,330
All right.

331
00:14:44,330 --> 00:14:45,830
So let's go there.

332
00:14:48,220 --> 00:14:49,660
So this is our DFS function.

333
00:14:49,660 --> 00:14:51,580
So let me just clean this up a bit.

334
00:14:55,110 --> 00:14:55,410
All right.

335
00:14:55,410 --> 00:15:00,480
So we are over here and we have called this function and vertex zero is passed to it.

336
00:15:03,030 --> 00:15:03,510
All right.

337
00:15:03,510 --> 00:15:07,320
So vertex zero this adjacency list and the visited object is passed.

338
00:15:07,320 --> 00:15:10,680
So we mark the particular vertex which is vertex zero.

339
00:15:10,680 --> 00:15:10,890
True.

340
00:15:10,890 --> 00:15:14,490
So we have zero true over here in our visited object.

341
00:15:14,490 --> 00:15:17,100
And then we are going to take the neighbors of zero right.

342
00:15:17,100 --> 00:15:18,810
So the neighbors of zero are just one.

343
00:15:18,810 --> 00:15:20,730
So there's just one neighbor.

344
00:15:20,730 --> 00:15:23,220
And then for I is equal to zero I less than one.

345
00:15:23,220 --> 00:15:24,450
So it's just going to iterate.

346
00:15:24,450 --> 00:15:28,950
One time we are going to take the neighbor at index zero which is one itself.

347
00:15:28,950 --> 00:15:31,650
And then we are checking whether one is visited.

348
00:15:31,650 --> 00:15:33,000
We see that it's not visited.

349
00:15:33,000 --> 00:15:37,440
So we are going to call the depth first search on vertex one.

350
00:15:37,440 --> 00:15:40,860
So again we come inside and over here we mark one visited.

351
00:15:40,860 --> 00:15:42,120
So we say one true.

352
00:15:44,030 --> 00:15:47,750
And then we are going to take the neighbors of one which is zero and one, right?

353
00:15:47,750 --> 00:15:50,810
So neighbors is going to be these two.

354
00:15:50,810 --> 00:15:52,400
This array is neighbors at this point.

355
00:15:52,400 --> 00:15:53,480
The length of it is two.

356
00:15:53,510 --> 00:15:55,670
So I initially is going to take zero.

357
00:15:55,670 --> 00:15:58,580
And we are going to take the neighbor at index zero which is zero.

358
00:15:58,580 --> 00:16:00,740
We see that it is already visited right.

359
00:16:00,740 --> 00:16:01,580
It's already visited.

360
00:16:01,580 --> 00:16:03,560
So we don't call DFS for it.

361
00:16:03,560 --> 00:16:06,530
And I increments to one and one is less than two.

362
00:16:06,530 --> 00:16:11,270
So we come inside and at index one the neighbor is this one over here.

363
00:16:11,270 --> 00:16:11,510
Right.

364
00:16:11,510 --> 00:16:12,170
This is zero.

365
00:16:12,170 --> 00:16:13,040
This is index one.

366
00:16:13,040 --> 00:16:14,150
So we get two.

367
00:16:14,150 --> 00:16:16,850
And then we check whether two is visited two is not visited.

368
00:16:16,850 --> 00:16:20,810
So we call the DFS function recursively and we pass the vertex two.

369
00:16:20,810 --> 00:16:21,920
So we come again inside.

370
00:16:21,920 --> 00:16:24,470
Over here we mark two as visited.

371
00:16:24,470 --> 00:16:26,360
So two is visited.

372
00:16:26,360 --> 00:16:29,720
So we have visited at two is marked as true.

373
00:16:29,720 --> 00:16:32,540
And then we are going to check the neighbors of two which is just one.

374
00:16:32,540 --> 00:16:34,460
And one is already visited over here.

375
00:16:34,460 --> 00:16:36,950
So we are not going to call the DFS function over here.

376
00:16:36,950 --> 00:16:42,680
So you can see that at this point all of these zero, one and two have been marked as visited.

377
00:16:42,680 --> 00:16:43,010
All right.

378
00:16:43,010 --> 00:16:45,800
So let's come back to our main function.

379
00:16:47,050 --> 00:16:50,740
So this was part of the call where we called this for zero.

380
00:16:50,740 --> 00:16:51,130
Right.

381
00:16:51,130 --> 00:16:53,350
So let me just clean this up a bit.

382
00:16:57,370 --> 00:16:59,740
So this was when vertex is equal to zero.

383
00:17:00,630 --> 00:17:06,750
So in in this case by doing DFS we went from 0 to 1 and from 1 to 2.

384
00:17:06,780 --> 00:17:09,120
So all of these have been marked as visited.

385
00:17:09,150 --> 00:17:13,110
Now when we are out of this vertex is going to increment to one.

386
00:17:13,110 --> 00:17:16,050
And we come over here and we see that one is already visited.

387
00:17:16,050 --> 00:17:17,880
So we don't call DFS for one.

388
00:17:17,880 --> 00:17:19,650
And this is incremented to two.

389
00:17:19,650 --> 00:17:22,140
And when we come to two we see that this is also visited.

390
00:17:22,140 --> 00:17:23,970
So we don't call DFS for two.

391
00:17:24,000 --> 00:17:25,500
This is incremented to three.

392
00:17:25,500 --> 00:17:28,380
And when we come to three we see that this is not visited.

393
00:17:28,380 --> 00:17:29,910
So we will increment the count.

394
00:17:29,910 --> 00:17:33,990
So count becomes two and then we will call DFS and we will pass three.

395
00:17:33,990 --> 00:17:36,660
So the vertex at that point is going to be three.

396
00:17:36,660 --> 00:17:39,390
And then when we come to three we will mark three as visited.

397
00:17:39,390 --> 00:17:39,780
Right.

398
00:17:39,780 --> 00:17:41,040
So three true.

399
00:17:41,310 --> 00:17:44,550
So that's going to happen over here in the DFS function.

400
00:17:44,550 --> 00:17:44,970
Right.

401
00:17:44,970 --> 00:17:47,730
So we have seen that we have we mark here visited true.

402
00:17:49,500 --> 00:17:50,910
Let's just clean this up.

403
00:17:52,670 --> 00:17:52,970
All right.

404
00:17:52,970 --> 00:17:54,770
So over here three is marked as true.

405
00:17:54,770 --> 00:17:57,470
And then we take the neighbors of three which is just four.

406
00:17:57,470 --> 00:17:59,060
And then DFS is called on it.

407
00:17:59,060 --> 00:18:00,980
So this is also marked as true.

408
00:18:00,980 --> 00:18:02,570
So four is also visited.

409
00:18:02,930 --> 00:18:04,400
And then we come out of this.

410
00:18:05,210 --> 00:18:11,060
So when we come back over here, vertex was three and then it's incremented to four.

411
00:18:11,060 --> 00:18:13,310
But when it gets to four we see it's already visited.

412
00:18:13,310 --> 00:18:15,230
So it does not come inside over here.

413
00:18:15,230 --> 00:18:16,850
And then it changes to five.

414
00:18:16,850 --> 00:18:19,070
And when we look at five this is not visited.

415
00:18:19,070 --> 00:18:20,840
So we increment the count.

416
00:18:20,840 --> 00:18:24,260
So we get three over here and we call the DFS with five.

417
00:18:24,260 --> 00:18:24,470
Right.

418
00:18:24,470 --> 00:18:28,100
So again inside the DFS this is going to get marked as visited.

419
00:18:28,100 --> 00:18:33,200
And we will call DFS on its neighbor which is six and six is not visited.

420
00:18:33,200 --> 00:18:35,060
So this is also marked as visited.

421
00:18:35,060 --> 00:18:36,290
And we come out of it.

422
00:18:36,290 --> 00:18:36,500
Right.

423
00:18:36,500 --> 00:18:38,240
So this was when vertex is five.

424
00:18:38,240 --> 00:18:41,690
So we are out again over here vertex is incremented to six.

425
00:18:41,690 --> 00:18:44,450
But at this point we see that six is already visited.

426
00:18:44,450 --> 00:18:46,820
So we don't call DFS for six and we are done.

427
00:18:46,820 --> 00:18:50,270
So we come out and we're just going to return the count which is equal to three.

428
00:18:50,270 --> 00:18:51,950
So this is how this function works.

429
00:18:51,950 --> 00:18:52,460
All right.

430
00:18:52,460 --> 00:18:54,500
So we have seen how this works.

431
00:18:54,500 --> 00:18:58,640
Now let's take a quick look at the space and time complexity of this solution.

432
00:18:58,640 --> 00:19:00,440
So let me just clear this up.

433
00:19:02,980 --> 00:19:05,170
So this is the function that we have written.

434
00:19:05,170 --> 00:19:08,260
Now let's take a look at the complexity analysis.

435
00:19:08,800 --> 00:19:11,920
So first let's take a look at this time complexity.

436
00:19:11,920 --> 00:19:14,230
So what's the time complexity of this solution.

437
00:19:14,230 --> 00:19:20,170
Let's take a look at the places where we have operations which will scale when the input will scale.

438
00:19:20,170 --> 00:19:22,900
So over here we are building the adjacency list right.

439
00:19:22,900 --> 00:19:24,820
So let's go to that part of the code.

440
00:19:25,810 --> 00:19:26,080
All right.

441
00:19:26,080 --> 00:19:28,840
So that's happening in this function right now.

442
00:19:29,440 --> 00:19:32,200
What is the number of operations that we are going to do over here?

443
00:19:32,200 --> 00:19:32,470
Right.

444
00:19:32,470 --> 00:19:37,930
So to build the empty adjacency list initially we are going to do v number of operations.

445
00:19:37,930 --> 00:19:38,320
Right.

446
00:19:38,320 --> 00:19:44,440
Because over here v or n is the number of vertices, n is the number of vertices v is also typically

447
00:19:44,440 --> 00:19:47,410
we use the word the letter v for the number of vertices.

448
00:19:47,410 --> 00:19:52,030
So over here we are building an empty array with v elements which are all empty right.

449
00:19:52,030 --> 00:19:52,630
Empty arrays.

450
00:19:52,630 --> 00:19:57,760
So over here we are going to do v operations because we have to loop through the array.

451
00:19:57,760 --> 00:20:00,100
And then we have to create these empty arrays over there.

452
00:20:00,100 --> 00:20:00,250
Right.

453
00:20:00,250 --> 00:20:01,930
So over here we have V operations.

454
00:20:01,930 --> 00:20:05,200
And then over here we are going to loop through the edges right.

455
00:20:05,200 --> 00:20:06,340
So we have this for loop.

456
00:20:06,340 --> 00:20:08,410
And let's say the edges is e.

457
00:20:08,410 --> 00:20:09,640
The number of edges is e.

458
00:20:09,670 --> 00:20:13,750
So over here again we are doing E operations because one operation per edge.

459
00:20:13,750 --> 00:20:19,570
So we can see that the build adjacency list function is going to do v plus e operations.

460
00:20:19,570 --> 00:20:21,970
Over here we have v plus e operations.

461
00:20:23,000 --> 00:20:26,030
And then let's come back to our main function.

462
00:20:26,030 --> 00:20:30,440
So over here also you can see that we are looping through all the vertices, right.

463
00:20:30,440 --> 00:20:32,930
We are looping through all the vertices at this point.

464
00:20:33,530 --> 00:20:35,420
So this is going to be v operations.

465
00:20:35,420 --> 00:20:38,510
And then we are going to call the DFS function right.

466
00:20:38,510 --> 00:20:41,960
The DFS function on the neighbors which are not visited yet.

467
00:20:41,960 --> 00:20:45,680
So again this over here is going to happen e number of times.

468
00:20:45,680 --> 00:20:46,010
Right.

469
00:20:46,010 --> 00:20:47,510
So let's take an example.

470
00:20:47,510 --> 00:20:53,840
Let's see let's for example take a graph where zero is connected to one which is connected to two.

471
00:20:53,840 --> 00:20:57,620
And then let's say three is connected to four which is connected to five.

472
00:20:57,620 --> 00:21:02,960
And at this point n is equal to six, or the number of vertices is equal to six.

473
00:21:02,960 --> 00:21:04,940
Now over here what will happen.

474
00:21:04,940 --> 00:21:09,140
Let's just trace this to understand that this also is actually v plus e.

475
00:21:09,260 --> 00:21:13,040
We are taking the vertices from 0 to 5 right.

476
00:21:13,040 --> 00:21:15,860
So that's going to be five operations.

477
00:21:15,860 --> 00:21:19,640
So let me just write that over here which is equal to v number of operations.

478
00:21:19,640 --> 00:21:21,740
So we see that zero is not visited.

479
00:21:21,740 --> 00:21:23,930
So a DFS call is made for this.

480
00:21:23,930 --> 00:21:26,030
So let me just write a tick mark over here.

481
00:21:26,030 --> 00:21:28,340
And then we come inside the DFS function.

482
00:21:28,340 --> 00:21:33,320
So let's see what happens over there inside the DFS function over here you can see we have this loop

483
00:21:33,320 --> 00:21:35,270
where we go through its edges.

484
00:21:35,270 --> 00:21:35,540
Right.

485
00:21:35,540 --> 00:21:38,840
So if this one over here has even edges right.

486
00:21:38,840 --> 00:21:43,070
So we will be doing even operations over here over here right in this for loop.

487
00:21:43,070 --> 00:21:44,540
Now let's go ahead.

488
00:21:44,540 --> 00:21:49,040
So we are going to call DFS recursively on edge one because it's not visited right.

489
00:21:49,040 --> 00:21:52,160
So at that point we are making a call a DFS call over here.

490
00:21:52,160 --> 00:21:54,080
So let me write a tick mark over here.

491
00:21:54,080 --> 00:22:00,770
And then when we are again inside this for this vertex we will make E two number of operations in this

492
00:22:00,770 --> 00:22:03,950
for loop where e two is the number of edges of this particular node.

493
00:22:03,950 --> 00:22:04,370
All right.

494
00:22:04,370 --> 00:22:09,260
So in this case we are going to go to two only because there is just one unvisited which is two right.

495
00:22:09,260 --> 00:22:13,670
But again it's going to do two operations because we are going to check if zero is visited.

496
00:22:13,700 --> 00:22:14,750
We will see it's visited.

497
00:22:14,750 --> 00:22:16,370
So we don't do an operation over here.

498
00:22:16,370 --> 00:22:17,660
And then we go to two.

499
00:22:17,690 --> 00:22:20,210
So let me write a tick mark over here recursively.

500
00:22:20,210 --> 00:22:22,940
We are again calling the DFS function with vertex two.

501
00:22:22,940 --> 00:22:27,950
And then once we are inside this we are going to have operations equal to the number of edges of this

502
00:22:27,950 --> 00:22:31,040
node over here, which just let me just write it as E three.

503
00:22:31,040 --> 00:22:34,160
So in this case it's just one and one is already visited.

504
00:22:34,160 --> 00:22:36,950
So we don't recursively call anything and we come out.

505
00:22:36,950 --> 00:22:39,860
So this is the total number of operations that we have so far done.

506
00:22:39,860 --> 00:22:41,930
Now let's come back to our main function.

507
00:22:41,930 --> 00:22:42,920
So we are over here.

508
00:22:43,930 --> 00:22:45,160
So we have done.

509
00:22:45,160 --> 00:22:46,960
At that point vertex was equal to zero.

510
00:22:46,960 --> 00:22:48,760
Now we go to vertex is equal to one.

511
00:22:48,760 --> 00:22:50,620
We see it's already visited.

512
00:22:50,620 --> 00:22:53,950
So we go ahead and we come to two that's already visited.

513
00:22:53,950 --> 00:22:55,270
So then we come to three.

514
00:22:55,270 --> 00:22:58,030
So when we come to three we see it's not visited.

515
00:22:58,030 --> 00:23:00,490
So we are going to make a call on vertex three.

516
00:23:00,490 --> 00:23:05,950
Again we come inside the DFS over here right again the DFS function which you've written over here.

517
00:23:05,950 --> 00:23:08,530
And at that point let me just write over here.

518
00:23:08,530 --> 00:23:13,840
We're going to make E for number of operations in this for loop where E4 is the number of edges with

519
00:23:13,840 --> 00:23:14,260
three.

520
00:23:14,260 --> 00:23:15,670
In this case it's just one.

521
00:23:15,670 --> 00:23:20,200
So we are recursively calling the DFS function for this particular node over here.

522
00:23:20,200 --> 00:23:24,850
Again we will do E5 operations where e5 is the number of edges of this node.

523
00:23:24,850 --> 00:23:29,740
And over here again we will visit the fifth vertex right if vertex five.

524
00:23:29,740 --> 00:23:34,270
And over here also let me say we are doing E6 operations in this for loop for that case.

525
00:23:34,270 --> 00:23:39,580
Now once we are out of this, we are back over here and then we will just go through four and five and

526
00:23:39,580 --> 00:23:41,830
we see that these are visited and we are out.

527
00:23:41,830 --> 00:23:44,800
So this is the total number of operations that's happening in this case.

528
00:23:44,800 --> 00:23:46,630
Now let's try to analyze this.

529
00:23:46,630 --> 00:23:48,100
How many operations are there.

530
00:23:48,100 --> 00:23:49,900
If we add up all of this right.

531
00:23:49,900 --> 00:23:55,150
If we add up all of these, we will see that we will get two into total number of edges.

532
00:23:55,150 --> 00:23:57,190
Because this is an undirected graph.

533
00:23:57,190 --> 00:24:01,750
So an edge between 0 and 1 will be counted for zero and as well as one.

534
00:24:01,750 --> 00:24:04,540
So that's why it will be two times the number of edges.

535
00:24:04,540 --> 00:24:08,650
Over here we are doing operations equal to two into the number of edges.

536
00:24:08,650 --> 00:24:10,960
So this is happening inside our DFS function.

537
00:24:10,960 --> 00:24:15,430
And then you can see over here we are doing vertex number of operations right.

538
00:24:15,430 --> 00:24:18,520
The number of operations because we are calling the over here.

539
00:24:18,520 --> 00:24:22,720
This for loop over here is actually going through each of these particular nodes.

540
00:24:22,720 --> 00:24:29,650
So we can see that in this place along with the DFS function we are doing a total of V plus two v operations.

541
00:24:29,650 --> 00:24:34,690
And again we have seen that in the case of building the adjacency list we are doing V plus E operations.

542
00:24:34,690 --> 00:24:40,570
So that's why we can say that the time complexity of this solution is of the order of V plus E.

543
00:24:41,290 --> 00:24:45,670
Again this constant can be neglected and we are getting v plus e over here as well as here.

544
00:24:45,670 --> 00:24:49,390
So the time complexity of this solution is equal to v plus e.

545
00:24:49,510 --> 00:24:51,580
Now what about the space complexity.

546
00:24:51,580 --> 00:24:53,200
So let me just clear this up.

547
00:24:53,200 --> 00:24:54,730
And I'm just writing it again.

548
00:24:54,730 --> 00:24:58,420
The time complexity of the solution is of the order of V plus e.

549
00:24:58,450 --> 00:25:00,760
Now what about the space complexity?

550
00:25:00,760 --> 00:25:05,200
We have seen that the things that take up space are the adjacency list which we are building.

551
00:25:05,200 --> 00:25:06,400
So that's the first thing.

552
00:25:06,400 --> 00:25:09,640
Then we have a visited object that takes up space.

553
00:25:09,640 --> 00:25:13,300
And then because we have written this solution recursively.

554
00:25:13,300 --> 00:25:15,610
So we are going to take up space on the call stack.

555
00:25:15,610 --> 00:25:19,690
So these are the three things that can take up space or auxiliary space.

556
00:25:19,690 --> 00:25:23,530
Now the adjacency list is going to have the vertices and the edges right.

557
00:25:23,530 --> 00:25:26,860
So this is going to take space of the order of v plus e.

558
00:25:27,340 --> 00:25:30,250
So we will have v number of arrays.

559
00:25:30,250 --> 00:25:33,430
And in each of these arrays right the edges would be represented.

560
00:25:33,430 --> 00:25:38,530
So that's why the space which is taken up by the adjacency list will be of the order of V plus e.

561
00:25:38,620 --> 00:25:40,180
So that's pretty straightforward.

562
00:25:40,180 --> 00:25:43,990
Now the visited object every vertex is going to be there.

563
00:25:43,990 --> 00:25:46,840
Finally in the visited object right once we have completed it.

564
00:25:46,840 --> 00:25:51,640
So this is going to take space of the order of V where v is the number of vertices, and then the call

565
00:25:51,640 --> 00:25:52,060
stack.

566
00:25:52,060 --> 00:25:58,240
In the worst case, if all the vertices are connected, the call stack can take up space of the order

567
00:25:58,240 --> 00:26:02,830
of V, because that's the maximum number of calls on the call stack, which can be there on the call

568
00:26:02,830 --> 00:26:04,150
stack at the same time.

569
00:26:04,150 --> 00:26:10,930
So we can see that based on this, the space complexity is going to be of the order of V plus E.