Hi,
I am doing AtCoder Beginner Contest 197F, and I have a question about the time complexity of the internal solution.
The usaco.guide solution has a time complexity of O(N^2 + M). But my question is - why not O(N^2 + M^2)?
I know it has N^2 because there are N^2 pairs of nodes i.e. the maximum total amount of states in the bfs. But I thought the second addend should be M^2 and I can prove it as follows:
Let the degrees of each node be d_1, d_2, d_3, ... , d_n for nodes 1, 2, 3, ..., N . The total number of pairwise products of these degrees is \sum_{i=1}^{N} \sum_{j=1}^{N} d_i * d_j = \sum_{i=1}^{N} d_i * \sum_{j=1}^{N} d_j = M * M = M^2
Thus, the total time complexity is O(N^2 + M^2)
How is it just O(N^2 + M)?
Either time complexity would easily pass given the constraints for the problem (N, M <= 1000) but I am still curious.