Introduction to Graphs: Definitions, Traversal, Depth-First Search

@kuruma Doing excellent work by writing good stuff.Here are some really straightforward ones
Try the pacman dfs and bfs.

1 Like

Thank you very much for this link @jaskaran_1 and I am glad you liked my post :slight_smile: It is amazing to see my work recognized and I really feel like I am learning new things now!! :slight_smile:

I got AC with DFS!!

And because of the ease of programming, me too, usually (or by default :stuck_out_tongue: ) 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 :slight_smile: ). 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 :slight_smile:

1 Like

Hello @vpyati, yes, I also really, really want to solve GALACTIK problem :smiley: I am eagerly waiting for editorials and although I have seen some AC solutions I want to understand everything at its fullest extent :slight_smile:

It’s nice to be appreciated @faiz :smiley: All I need now is to train hard so I can start applying all these ideas to contest problems :slight_smile:

@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

1 Like

Thank you very much @kcahdog :slight_smile: I really tried very hard to solve GALACTIK during contest, but, I couldn’t :frowning:

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 :slight_smile:

@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 :slight_smile:

1 Like

GALACTICK could be solved using Disjoint Sets data structure instead of DFS and BFS. This would have sped up the code by many times :slight_smile:

Thank you @v_akshay, I’m glad you liked this :slight_smile: About the asked vs posted part, as this was a “question”, it says asked, but, I guess that is just how the forums work :slight_smile:

Thank you very much for the positive feedback @re_hash! I hope I can implement all these ideas in next contests myself as well :smiley:

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

1 Like

its really helpful thanks!!

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 ?