There are n basketball teams in the world. The ranking of these teams from the previous year is available. This year, some of these n teams played against each other and the winner of each game was determined. There were m games in total. The International Basketball Association wants to introduce a new performance criterion, called “domination factor”, defined as follows: Team i is said to “dominate” team j if we can find a chain of games such that j was beaten by a team that was beaten by a team that was beaten by a team ... that was beaten by i (observe that, according to this definition, domination can be bi-directional, i.e., i and j can dominate each other). Then, for each team i, the domination factor Di is defined as the rank of the best team (that is, the highest ranked team according to last year’s rankings) that is dominated by team i.
Use DFS to devise an O(m + n) time algorithm to compute the domination factor for all the n teams.