TriangleFree
SRM 693 · 2016-06-04 · by jcvb
SRM 693 · 2016-06-04 · by jcvb · Dynamic Programming, Graph Theory
Problem Statement
Problem Statement
You are given an undirected graph with n vertices numbered 0 through n-1.
For each valid i, there is an undirected edge connecting two different vertices x[i] and y[i].
No two edges connect the same pair of vertices.
A triangle is a set of three distinct vertices such that each pair of those vertices is connected by an edge. Formally, three distinct vertices u,v,w are a triangle if the graph contains the edges (u,v), (v,w), and (w,u).
The graph has 2^n subsets of vertices (including the empty set). A subset S of vertices is called triangle-free if and only if no three vertices in S form a triangle.
You are given the description of the graph: theint n and the int[] s x and y.
Compute and return the number of triangle-free subsets of vertices of the given graph.
A triangle is a set of three distinct vertices such that each pair of those vertices is connected by an edge. Formally, three distinct vertices u,v,w are a triangle if the graph contains the edges (u,v), (v,w), and (w,u).
The graph has 2^n subsets of vertices (including the empty set). A subset S of vertices is called triangle-free if and only if no three vertices in S form a triangle.
You are given the description of the graph: the
Constraints
- n will be between 1 and 60, inclusive.
- x will have between 0 and 60 elements, inclusive.
- y will have the same number of elements as x.
- Each element of x and y will be between 0 and n-1, inclusive.
- For each valid i, x[i] != y[i].
- No two edges will connect the same pair of vertices.
Examples
0)
4
{0,1,2,3}
{1,2,0,2}
Returns: 14
There are 2^4 = 16 subsets in total. Two of them are not triangle-free: {0,1,2} and {0,1,2,3}.
1)
5
{0,0,0,0,1,1,1,2,2,3}
{1,2,3,4,2,3,4,3,4,4}
Returns: 16
This is a complete graph. Any subset having more than two vertices is not triangle-free.
2)
6
{0,0,1,1,1,3,1,2,2,4}
{1,2,2,3,4,4,5,4,5,5}
Returns: 40
3)
60
{10,20,30}
{20,30,10}
Returns: 1008806316530991104
4)
60
{14,18,14,9,15,17,18,14,10,6,17,19,19,5,3,17,5,19,15,1,13,13,16,4,12,11,19,12,9,16,8,11,16,13,13,14,14,14,2,15,12,17,4,6,18,16,12,13,11,16,19,19,19,17,10,17,19,14,5,9}
{8,16,13,4,5,14,11,5,6,2,10,3,17,4,0,12,3,10,6,0,6,5,9,1,2,2,2,8,1,7,4,1,10,4,11,9,1,0,1,7,9,8,2,3,3,8,3,8,10,0,4,7,5,13,8,11,0,11,1,8}
Returns: 209857187323838464
Submissions are judged against all 109 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class TriangleFree with a public method long long count(int n, vector<int> x, vector<int> y) · 109 test cases · 2 s / 256 MB per case