Topological sorting on strings

#1

how to use topological sorting on strings or words
like int a quetion of codeforces 510C
can u plz tell me how to make graph in such que to and implemement tps??

#2

Hey @Ashu1318
Please share the link to the question:)

#3

https://codeforces.com/problemset/problem/510/C

#4

Here like this we will make graph in this situation

#5

okay after marking edges acc to ur code when i dry run adj matrix for topological sorting it give wrong ans i mean after marking edges true acc to cond first we have to take thode char which are not true acc to topological sorting??

#6

Can u please elaborate with the help of example u used for dry run and the matrix u obtained :slight_smile:

#7

yaah test case 1 of the same problem 510C on cf, here i make edges of char b/w string 1 and string 2,now we have print those char first which are not connected something like indegree now in this example i make egde with s&h both so can i come first before s??

#8

See
Here

3
rivest
shamir
adleman

The strings are sorted
so what we can say for certain is
r comes before s
and s comes before a
So we connect only these 2 edges
and then apply our algo

There can be multiple correct answers