@kuruma Doing excellent work by writing good stuff.Here are some really straightforward ones
Try the pacman dfs and bfs.
Thank you very much for this link @jaskaran_1 and I am glad you liked my post It is amazing to see my work recognized and I really feel like I am learning new things now!!
I got AC with DFS!!
And because of the ease of programming, me too, usually (or by default ) use DFS!!!
Hey @tijoforyou, yes, I was perfectly aware that such arrays are not only there for the sake of completeness and might really be needed at some point (just as you showed ). I opted for not including them to keep the text as introductory as possible and also because it was what it was mentioned on that russian website link I provided
Hello @vpyati, yes, I also really, really want to solve GALACTIK problem I am eagerly waiting for editorials and although I have seen some AC solutions I want to understand everything at its fullest extent
Itās nice to be appreciated @faiz All I need now is to train hard so I can start applying all these ideas to contest problems
@kuruma Even i am new to graphs and GALACTIK is the only graphs problem i have solved so far. Will keep you updated if i find any interesting problems
Thank you very much @kcahdog I really tried very hard to solve GALACTIK during contest, but, I couldnāt
Interestingly, GALACTIK can also be solved using the Disjoint-Set Data structure. My solution was based on DFS. But out of curiosity (as I was lazy, didnāt try this version), once the contest was over, I checked if someone has solved it using Disjoint-Sets, and found @mugurelionutās solution.
Thanks for your positive feedback sir
@admin , why does it say āasked n days ago by kurumaā shouldnāt it rather say āposted n days ago by kurumaā ? btw @Kuruma, really nice and helpful post
GALACTICK could be solved using Disjoint Sets data structure instead of DFS and BFS. This would have sped up the code by many times
Thank you @v_akshay, Iām glad you liked this About the asked vs posted part, as this was a āquestionā, it says asked, but, I guess that is just how the forums work
Thank you very much for the positive feedback @re_hash! I hope I can implement all these ideas in next contests myself as well
Do we have a āstatic algo tutorials pageā here on Discuss? The closest thing seems to be the tutorials and references posted at Codechef for Schools page, but, if we could pin a āsub-forumā grouping all tutorials or even better all editorials on its own āsub-forumsā, that would be really useful
I solved the problem first by Disjoint Sets and then by DFS. Learned a lot about DFS from GALACTIK that helped me in FEB14 in solving DRGHTS.
It tells that a particular friend has sz_connct_compt number of connected friends.
Means, if 1->2 and 2->3 and 3->5,6
so when we dfs(1) the sz_connct_compt will become 5, as there are 5 friends that will be liking to escape by same route.
I hope now you have understood. @amanjain7793
What would be the time complexity to find indegree and outdegree of a vertex in qdjecency list ?