BuildingSpanningTreesDiv1
SRM 733 · 2018-04-13 · by ltdtl
Problem Statement
Consider an undirected, complete, simple graph G on n vertices. The vertices of G are labeled from 1 to n. Specifically, each pair of distinct vertices is connected by a single undirected edge, so there are precisely n*(n-1)/2 edges in this graph.
You are given a set E that contains some edges of the graph G.
More precisely, you are given the
A spanning tree of G is a subset of exactly n-1 edges of G such that the edges connect all n vertices. You may note that the edges of a spanning tree do indeed form a tree that is a subgraph of G and spans all its vertices.
We are interested in spanning trees that contain all of the edges in the provided set E. Compute and return the number of such spanning trees modulo 987,654,323. Two spanning trees are different if there is an edge of G that is in one of them but not in the other.
Notes
- 987,654,323 is a prime number.
Constraints
- n will be between 1 and 1,000, inclusive.
- x will contain between 1 and 1,000 elements, inclusive.
- y will contain between 1 and 1,000 elements, inclusive.
- x and y will contain the same number of elements.
- Each element of x will be between 1 and n-1, inclusive.
- Each element of y will be between 2 and n, inclusive.
- For each valid i, x[i] will be less than y[i].
- All edges in E will be distinct.
3
{1,2}
{2,3}
Returns: 1
The edges in the provided set E alredy form a spanning tree, so there is exactly one spanning tree that contains them.
5
{1,3,4}
{2,4,5}
Returns: 6
There are six ways to add the one missing edge: one endpoint of the new edge must lie in the set {1,2} and the other in the set {3,4,5}.
4
{1}
{2}
Returns: 8
There are eight spanning trees that contain the edge (1, 2): {(1, 2), (1, 3), (1, 4)} {(1, 2), (1, 3), (2, 4)} {(1, 2), (1, 3), (3, 4)} {(1, 2), (2, 3), (2, 4)} {(1, 2), (1, 4), (2, 3)} {(1, 2), (1, 4), (3, 4)} {(1, 2), (2, 3), (3, 4)} {(1, 2), (2, 4), (3, 4)}
4
{1,2,1}
{2,3,3}
Returns: 0
The set E contains a cycle, and thus there is no spanning tree that contains all these edges.
8
{1,4,2,3,5}
{4,7,6,5,8}
Returns: 144
1000
{1}
{2}
Returns: 529013784
Don't forget to take the modulo.
Submissions are judged against all 151 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BuildingSpanningTreesDiv1 with a public method int getNumberOfSpanningTrees(int n, vector<int> x, vector<int> y) · 151 test cases · 2 s / 256 MB per case