Connection Status:
Competition Arena > BFSOrder

BFSOrder

2020 TCO Final · 2020-11-12 · by misof

2020 TCO Final · 2020-11-12 · by misof · Dynamic Programming
Class Name: BFSOrder
Return Type: int
Method Name: count
Arg Types: (vector<int>)
Problem Statement

Problem Statement

In this problem we consider a specific implementation of breadth-first search (BFS). The input is an undirected graph on N vertices. The vertices are labeled from 0 to N-1. The graph is simple (i.e., no self-loops and no multiple edges). The specific property of our BFS is that whenever we process neighbors of a vertex, we do so in numerical order (smallest to largest).

For reference, the pseudocode of the algorithm is given below. (You should not need it. It's just ordinary BFS in lexicographic order.) 


BFS(start):
    visited = an empty set
    visited.add(start)
    Q = an empty queue
    Q.push_back(start)

    while Q is not empty:
        current = Q.pop_front()
        for next in 0 .. N-1:
            if (next is not in visited) and (there is an edge between current and next):
                visited.add(next)
                Q.push(next)

The BFS order of a connected graph is a permutation of its vertices in the order in which they would be processed if we start the BFS described above from vertex 0. (A vertex is processed when it's popped from the queue.)

You are given the int[] bfsOrder: a permutation of numbers 0 to N-1 that starts with 0.

Count all connected simple graphs with this BFS order, and return that count modulo 10^9 + 7.

Constraints

  • N will be between 1 and 3000, inclusive
  • bfsOrder will be a permutation of numbers from 0 to N-1, inclusive.
  • bfsOrder[0] will be 0.
Examples
0)
{0, 1, 2}
Returns: 3

Three of the four connected graphs on three vertices have this BFS order. Here they are: 0--1--2 0--1 0--1 | | / | |/ 2 2

1)
{0, 2, 1}
Returns: 1

The one remaining connected graph on three vertices (with edges 0-2 and 2-1).

2)
{0, 1, 3, 2}
Returns: 7

One of these seven graphs is the path 0-1-3-2, in the other six the neighbors of 0 are 1 and 3.

3)
{0, 6, 5, 4, 2, 3, 1}
Returns: 7

For each BFS order there is always at least one valid graph (the path with the vertices in that order). Sometimes there is more than one, sometimes there isn't.

4)
{0}
Returns: 1
6)
{0, 2, 1, 4, 3, 5}
Returns: 37

One of those graphs: 0--2--1--3 | /| / |/ |/ 4--5 Our BFS will start in 0, discover 2 as a neighbor of 0, discover 1 and 4 (in this order) as neighbors of 2, and finally discover 3 and 5 (again, in this order) as neighbors of 1. Another one of those graphs: 0--2--1--3 | / | / 4--5 Here, the last vertex (5) will only be discovered when processing vertex 4. Still, the order in which the vertices of this graph are processed remains the same: 0, 2, 1, 4, 3, 5.

Submissions are judged against all 127 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class BFSOrder with a public method int count(vector<int> bfsOrder) · 127 test cases · 2 s / 256 MB per case

Submitting as anonymous