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

tutorial
, ,
21

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

1 Like
22

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:

23

I got AC with DFS!!

24

And because of the ease of programming, me too, usually (or by default :stuck_out_tongue: ) use DFS!!!

25

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
26

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:

27

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:

28

@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
29

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

30

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.

31

Thanks for your positive feedback sir :slight_smile:

32

@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
33

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:

34

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:

35

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:

36

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
37

@Kuruma
its really helpful thanks!!

38

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.

39

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

40

What would be the time complexity to find indegree and outdegree of a vertex in qdjecency list ?