Algorithm Class - Breadth First Search 4

Seojun is assisting in a breadth first search (BFS) class again today. Let us check through a problem whether the students understood what his father taught.

We are given an undirected graph with N vertices and M edges. The vertices are numbered from 1 to N, and every edge has weight 1. The tree produced by a breadth first search starting at vertex R is called a breadth first search tree. Let di be the depth of node i in the breadth first search tree. The depth of the start vertex R is 0, and the depth of an unvisited node is -1. When nodes are visited by a breadth first search starting at vertex R, let ti be the visit order of node i. The visit order of the start vertex is 1, and the visit order of a node unreachable from the start vertex is 0. Find the sum of di × ti over all nodes.

The pseudocode for the breadth first search is as follows. Adjacent vertices are visited in ascending order.

bfs(V, E, R) {  # V : vertex set, E : edge set, R : start vertex
    for each v ∈ V - {R}
        visited[v] <- NO;
    visited[R] <- YES;  # mark the start vertex R as visited.
    enqueue(Q, R);  # add the start vertex R to the back of the queue.
    while (Q ≠ ∅) {
        u <- dequeue(Q);  # remove the element at the front of the queue.
        for each v ∈ E(u)  # E(u) : set of vertices adjacent to vertex u. (visited in ascending vertex number order)
            if (visited[v] = NO) then {
                visited[v] <- YES;  # mark vertex v as visited.
                enqueue(Q, v);  # add vertex v to the back of the queue.
            }
    }
}

The first line gives the number of vertices N (5 ≤ N ≤ 100,000), the number of edges M (1 ≤ M ≤ 200,000), and the start vertex R (1 ≤ R ≤ N).

The next M lines give edge information u v, representing an undirected edge of weight 1 between vertex u and vertex v. (1 ≤ u < v ≤ N, u ≠ v) All (u, v) pairs are distinct.

On the first line, print the sum of di × ti over all nodes.