codeforces 510C help needed to understand requirement of DFS

codeforces
dfs
graph
medium

#1

Heres what i did:

  1. find if all similar names are lexo sorted (i.e. those having least one char i.e. first one same (will be grouped together)), if so…


    probably rearranging alphabets, a solution would be possible…

  2. print alphas starting from ‘a’…‘z’ till first elements first char (which don’t appear in any names)

  3. print all names first char (avoid repetition), as all similar will be grouped and are lexo-sorted as above checked else would have been impossible.

  4. print the rest one’s (alphabets) that didn’t appear in list.



    Though i tried looking at someone else code and test cases, i got the code but where can a loop occur or why do i need a dfs, if anyone could give me an example i.e. test case i will be thankful to him/her. Thanks in advance. tried it but " failed at 12th test case " , feel free to point out my mistake in

    Wrong code Link case 12 failed and Problem link.




    Like in first example,… print all alphabets from ‘a’ to till ‘r’ i.e. first alphabet of first name, excluding those that appear somewhere as first alphabet in any name, i.e. form ‘b’ to till ‘q’ and then all names first alphabets then again starting from ‘r’ to till ‘z’ that haven’t been printed, so solution becomes


    alpha + names alpha + remaining alphas =

    “bcdef…q” + “rsa” +“tuvwxyz” = bcde…q rqsa tuv…z

    Probably logic is wrong, but couldn’t find the need of dfs in the question. PLEASE HELP!!!

#2

DFS is used to generate topological sort. You can actually make a directed graph of 26 nodes where each node denotes the alphabet. Edges are added according to the precedence of each alphabet that is generated by comparing each pair of two strings.


#3

thanks apptica :slight_smile:


#4

i asked the same question, same format on codeforces, via a blog and i was down voted rather than answering, where else or what way shall i ask questions then? can you please help me!