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 vector s x and y. For each valid i, (x[i], y[i]) is one of the edges in E.
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.
Definition
Class:
BuildingSpanningTreesDiv1
Method:
getNumberOfSpanningTrees
Parameters:
int, vector , vector
Returns:
int
Method signature:
int getNumberOfSpanningTrees(int n, vector x, vector y)
(be sure your method is public)
Limits
Time limit (s):
2.000
Memory limit (MB):
256
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.
Examples
0)
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.
1)
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}.
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stdint.h>
#include <string>
#include <utility>
#include <vector>
using namespace std;
int const MAX_N = 1003;
int const MOD = 987654323;
int p [MAX_N];
int s [MAX_N];
int root (int v)
{
if (p[v] != v)
{
p[v] = root (p[v]);
}
return p[v];
}
bool unite (int u, int v)
{
u = root (u);
v = root (v);
if (u == v)
{
return false;
}
p[v] = u;
s[u] += s[v];
return true;
}
int powmod (int a, int b)
{
int res = 1;
for ( ; b > 0; b >>= 1)
{
if (b & 1)
{
res = (res * 1LL * a) % MOD;
}
a = (a * 1LL * a) % MOD;
}
return res;
}
int a [MAX_N] [MAX_N];
int n;
int det (void)
{
int res = 1;
for (int i = 1; i < n; i++)
{
int j;
for (j = i; j < n; j++)
{
if (a[j][i])
{
break;
}
}
if (j == n)
{
return 0;
}
if (j != i)
{
for (int k = i; k < n; k++)
{
swap (a[i][k], a[j][k]);
}
}
res = (res * 1LL * a[i][i]) % MOD;
int inv = powmod (a[i][i], MOD - 2);
for (int j = i + 1; j < n; j++)
{
int mult = (a[j][i] * 1LL * inv) % MOD;
for (int k = i; k < n; k++)
{
a[j][k] = (a[j][k] -
a[i][k] * 1LL * mult) % MOD;
}
}
}
return (res + MOD) % MOD;
}
class BuildingSpanningTreesDiv1
{
public:
int getNumberOfSpanningTrees (int n, vector <int> x, vector <int> y)
{
for (int i = 0; i < n; i++)
{
p[i] = i;
s[i] = 1;
}
int k = (int) (x.size ());
for (int w = 0; w < k; w++)
{
int u = x[w] - 1;
int v = y[w] - 1;
if (!unite (u, v))
{
return 0;
}
a[u][v] += 1;
a[v][u] += 1;
a[u][u] -= 1;
a[v][v] -= 1;
}
int t = 0;
for (int i = 0; i < n; i++)
{
if (p[i] == i)
{
s[t] = s[i];
t += 1;
}
}
n -= k;
::n = n;
memset (a, 0, sizeof (a));
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
int e = s[i] * s[j];
a[i][j] -= e;
a[j][i] -= e;
a[i][i] = (a[i][i] + e) % MOD;
a[j][j] = (a[j][j] + e) % MOD;
}
}
int res = det ();
return res;
}
};
