Why does this algorithm work in O(n m)?

Question

This is from a blog post on Codeforces. I couldn't really understand why the editorialist goes on to claim that this code works in O(n m)

This is a graph problem, where we are supposed to find the number of ways to traverse from a to c. Note that only the paths like a-->b-->c and a-->d-->c need to be considered. That is, there should be a difference of only one node, in between them.

n is the number of vertices, m is the number of edges and nxt is the adjacency list.

Let's iterate through all combinations of a and c just two simple nested loops in O(n^2) and find all candidates for b and d inside. To find candidates you can go through all neighbors of a and check that they are neighbors of c. Among all the candidates you should choose two junctions as b and d. So just use https://en.wikipedia.org/wiki/Combination All you need is to add to the answer , where r is the number of candidates (common neighbors of a and c). The code is:

for (int a = 0; a < n; a++)
    for (int c = 0; c < n; c++)
        if (a != c)
        {
            int r = 0;
            for (int b = 0; b < nxt[a].size(); b++)
                if (nxt[a][b] != a && nxt[a][b] != c && g[nxt[a][b]][c])
                    r++;
            result += r * (r - 1) / 2;
        }

It is easy to see that the total complexity is O(nm), because of sum of number of neighbors over all junctions is exactly m.

If there are 3 loops involved, then how can the worst case complexity be O(n m)

Answer 1

The outer loop has n iterations.

The middle loop has n iterations.

The inner loop has deg(a) iterations. This is because the nxt array is adjacency list of the graph, which means nxt[a] is a list of all edges going from vertex a and therefore nxt[a].size() is (out) degree of a.

Because m, the number of edges, is ∑_a deg(a), the inner two loops together make m iterations and times the outer n is the result.

---

Notes: The test whether edge from nxt[a][b] to c exists is O(1), because g is incidence matrix. It is a bit unusual to see both adjacency list and incidence graph representations, because they both have to be prepared. The usual approach is to use adjacency list for sparse graphs, i.e. those with m ~ O(n), because then deg(a) ~ O(1) and linear search in the for the follow-up edge is constant-time, and to use incidence matrix for dense graphs, i.e. those with m ~O(n²), because then the O(n m) = O(n³) anyway, so looping over all vertices instead of out edges in the inner loop does not matter.

The other issue is that the author of this should be condemned for the choice of variables. It is usual for mathematical algorithms to use single-letter variables, but at least variable indicating index into the adjacency list should not be taken from the same range as variables for vertices. I'd use customary u and v for vertices (that is u = a and v = c) and i for index (that is i = b).