TriangleEasy
SRM 693 · 2016-06-04 · by jcvb
SRM 693 · 2016-06-04 · by jcvb · Graph Theory, Greedy
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).
You are given the description of the graph: theint n and the int[] s x and y.
You are allowed to add edges to this graph.
You may add as many edges as you want, and each of them may connect any two vertices.
Your goal is to produce a graph that contains at least one triangle.
Compute and return the smallest number of edges you need to add.
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).
You are given the description of the graph: the
Constraints
- n will be between 3 and 50, inclusive.
- x will have between 0 and n*(n-1)/2 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)
3
{}
{}
Returns: 3
The graph has three vertices but no edges. You need to add edges (0,1), (1,2), and (2,0) to make it a triangle.
1)
4
{0,2,1,2}
{3,0,2,3}
Returns: 0
Note that the edges are undirected. The graph already has a triangle: (2,0),(0,3),(2,3), so we don't have to add anything.
2)
6
{0,0,2}
{3,1,4}
Returns: 1
3)
5
{1,1,2,2,0,0,1,3,2,2}
{0,4,1,3,3,4,3,4,4,0}
Returns: 0
4)
4
{0,2}
{1,3}
Returns: 2
Submissions are judged against all 103 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class TriangleEasy with a public method int find(int n, vector<int> x, vector<int> y) · 103 test cases · 2 s / 256 MB per case