I am solving UVa–1229 https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=671&page=show_problem&problem=3670 From the problem I have understood what is required – given a list of dictionary words and their definitions, choose minimum set of words such that the whole dictionary can be constructed, if one is given meaning of those words. So words in dictionary must not introduce a new word in definition which has no meaning in dictionary. This implies I have to find SCC.
But there may be several SCCs, I think I must choose which is first in toposort of contracted DAG. Am I correct or is there another way to do it? I have read hints but its’ mentioned to find SCC, then use dfs that will be answer. I don’t get that. Can someone explain approach to this problem.
That’s my first question on SCC’s 🙂