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.
Let's call the teams $$$a_i$$$, $$$a_1$$$ being the best and $$$a_n$$$ is the worst.
Call a dfs from $$$a_1$$$ in the transpose graph(edges reversed). We know for sure that their $$$D$$$ values are 1. After that we can simply remove all the nodes we traversed in this process. The reason is if any other node can reach to one of these nodes, then they'd be simply traversed in the first place and their $$$D$$$ values would be 1.
After that take the minimal $$$i$$$ such that $$$a_i$$$ isn't removed yet and do the same process again.
In total we'll end up being traversed just the graph, thus time complexity will be $$$O(m+n)$$$.
I am having trouble understanding the solution. Based on the nature of question, if a1 plays a2 (this would also mean a2 plays a1), so the graph is bidirectional graph.
Apart from the above very basic questions, I could still not understand the algorithm. Can you expand on it a little more.
What did you google to find this blog?