Count the Number of Complete Components - Leetcode 2685 - Python

Key Takeaways

Hey everyone, welcome back and let's write some more neat code today. So today, let's solve the problem. Count the number of complete components. The idea is that we are given an integer n which is going to represent the number of vertices in our graph. So you can see that we are given six. We have six vertices here. They are not necessarily a part of a single component though because that's what this problem is all about. We want to count the number of components. But it's not as straightforward as just counting that like this is one, this is two, and this is three because there is actually a little rule to this game. We only care about complete connected components. And what that basically means in this problem is that every single vertex, a part of a component, so this is one component, this is a separate component, and this is a third component. For all of these components, we sort of just want to count which one of them are actually complete. So looking at the first component, this is how it's going to work. We look at every single vertex in the component to make sure that there is an edge from every single node to every other node in that component. What that means is just to draw it out. If I have just a single node, well then that's satisfied because like this what I have circled there just needs to exist an edge from one node to every other node. We just have a single node here. When we have two nodes, we just need one edge connecting them together. When we have three nodes, I'm going to draw the node over here. We need three edges connecting them together. With a four nodes, we end up with something kind of like this where we have an edge going from every other edge. So from this node, we have an edge going to every other edge. Same thing here. Same thing here. And same thing here. So that's what we're checking for. And you can see that for each of the components up above that is true. This one is complete. This one is complete. And this one is complete. So we counted three in total. Three is what we would return. So, conceptually, I think what we're trying to do is actually sort of simple because this is a pretty simple description, but knowing a little bit about graph theory and how to run an actual traversal like DFS or BFS is going to be pretty necessary to solve this problem. That's what I'm going to be walking you through. And I think since this graph is undirected, we could also probably do union find as well, but that's usually more complicated. There's mainly going to be two steps to this algorithm. The first is going to be of course getting the actual components like separating them out. We need to be able to somehow distinguish that five is a part of its own component. That 0, 1, and two are a part of the same component. Three and four are a part of the same component as well. Many many different ways to do this. DFS, BFS, or union find. There might be some others as well, but I think it's perfectly fine to just use a simple traversal. You can pick whichever one of these is easiest for you or maybe one of the more difficult ones if you want to practice. But the only thing we're trying to do with this first phase is just split the nodes. So for every node, I could just run a traversal. I could run a DFS starting from every node to get all the components. So for five, there's nowhere to go. This is its own component. Then maybe I go to zero. I see zero. and then I go to one and then I go to two and then I say okay well this is a component there's nothing else to see then I go to three and then I get the same thing here and maybe if I revisit the same node that's already been visited if I got to two next I would see that two is already a part of its own component we don't need to traverse it again so we could do that just by iterating from zero up until n minus one and just running a dfs for everything on that the next part is in my opinion pretty easy. Once you have all the nodes for a given component, if I got this, if you gave me those nodes, the next thing what I would do is just count the edges and then determine if that component is valid or not. If it is, you increment the count. If it's not, you don't. There's multiple ways to count the edges as well. One thing you could do is compare the number of nodes to the number of edges because what you can see is happening every single time for each node. Like in a component if there's nodes in this example there's three. Well, for each node there's going to be two edges going out of it because it's connected to the other nodes. It's this number minus one is going to get you that. So arbitrarily if I had nodes, I know each of those nodes is going to have n minus one edges uh coming out of it. So that's pretty much what you could do. For every single node, check that there's n minus one where n is the size of that component. There's n minus one edges connected to that node. That's pretty much I think all I have to say in terms of time and space. I think it's just going to be dependent on the size of the graph. So it should be the number of vertices plus edges. So I'm going to define my DFS here, but I'm going to show you how I use it first. I'm just going to have a couple variables. One is the vertex that we're going to run the DFS from. And the other is going to be result. I want to show you how I use this function before I implement it. Because what I'm going to do is for every single vertex that we have available, I want to run a DFS on it. I want to say dfs from this vertex. And I'm going to pass in an empty array. And what this array is going to be is all of the nodes that belong to this component that belong to the one connected to this node. So it's going to return that array that I'm passing in here. You're probably wondering, why don't I just create the array inside of there? Well, it's recursive, so that would be less efficient because there's going to be a lot going on if I do that. So I'm just doing it this way. We can expect that it's going to return the array that is the component. All of the nodes should be in here. Now, we want to guard this recursive step with an if statement because if v is in visit, that means that this node has already been visited before probably because it was connected to somebody else that we already visited and therefore we can just continue. We can skip this node. Otherwise, we do this and then we want to know I'll write this code in a couple different ways because this is kind of the easy part. Well, first of all, down here we're just going to return the result. Result initially I will say is going to be zero and also I will say I have a visit hash set and this hashet will be accessible inside of this function even though we don't pass it in there. I also could have like declared an array out here and then not passed it in to the function, but I think it just makes it a little bit more clear here since this result is only being used for this function. Whereas the visit hash set, it's going to be used for all invocations of that function. But now for all of these nodes, I want to do this for I guess I'll say V in component. I'm kind of reusing that, but I guess I'll call it V2. for v2 in component all the vertices in there I'm going to have a variable I guess I'll just call it my flag initially I'll set it to true but if we ever see a node where this is not the case if the length of the entire component minus one is not equal uh I'll do not equal to the length of the edges connected to v2 which I'm going to use an adjacy list for that So adjacy list of v2. If this is not the case, we're going to set our flag to false and we're going to break out of the loop. So then out here, we would know if my flag is true, that means my result is valid and I can then increment the result. Now this code will work. I promise you that it'll work. But if you want to join the church of Python, let me show you a way you can make this code much more concise. I'll leave the code here because I'm basically going to replace it with a oneliner. If you are interested, Python has this function called all. So, we're going to do this if all. So, we're going to pass in an array into this function which I'm going to build in line. I'm going to go through pretty much what I did down there for every vertex in the component verticy. And I guess I'll just copy and paste uh this and then change the equal sign. So if this is equal, so this is basically going to create an array of booleans like these booleans pretty much similar except it's the opposite. And then it's going to check if everything in here is true. So that this is checking the opposite. It's checking that it is valid. This was checking if it was invalid. So if this is true, well then we don't even need a flag. We can just increment our result. So the time complexity of this code and this code is the exact same. It's just this is a bit more readable. in my opinion, but for you it might be less readable. Anyways, I will leave that code there now and the rest of this is just finishing up a relatively simple DFS. So now we will add the base case of course if V is already visited. If it's in the visit hash set, then we can return. Now I could return the result here, but we would never expect of a function call from down here for us to return immediately from the base case. So you actually don't need that here. You can leave it there if you want, but it's not going to do anything and I won't put it there. So next, if it's not visited, well then we should probably add it to the visit hash set and then traverse the neighbors. So something like this. But before we do that, let's remember what we're trying to do in this function. We just want to collect every vertex. So here before we return or even before we go to the neighbors, let's add this node to the result. And that is the one that we're going to return from this function. And in the function, all we do is just call DFS on the neighbor, passing in the same result array from up above. This is a simple DFS. We make sure we don't get stuck in any cycles and we just return the nodes belonging to each component. I think the only thing I'm forgetting at this point is actually creating that adjacy list. So, let's not forget that it was not given to us, but we were given the list of edges up above. So we can do something like this where I will end up using a default dictionary where the default value will be a list. So I can do this for vub1 v2 in edges and then just map them both ways because we know that this is an undirected graph. So like this and then I think we are done. So running this code you can see here that it works. It's pretty efficient. It looks like the memory isn't super efficient, but I'm pretty sure it's a pretty small difference. You can see that it's like a.3 megabyte difference. Not a big deal in my opinion. I think maybe some of the other variations probably have a better memory, but this one does have a pretty good runtime. If you found this helpful, definitely check out Necode.io, especially if you want to learn like these Python tricks and you don't know like what a default dictionary is and stuff like that. I have a lot of resources on there to help you