Topological sort problem

给定输入这样的字符串
fft, fcp, aac, act, acd, atp, tbk, tdf, …
这些都是按照字母排序好的,但是字母顺序改了,比如 f 在 a之前,t在d之前等等,
问怎么rebuild the alphabet according to those rules?

Answer: topological sort
we have all the nodes which are the alphabets, then we have all the edges which are the f->t, f->c, c->p, a -> c…. which can be get from the input string. Then we do a topological sort on all the nodes. we can get the alphabets that follow the rules implied by the input string.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s