SixDegreesOfSeparation
TCO17 Regional Wildcard · 2017-03-31 · by cgy4ever
TCO17 Regional Wildcard · 2017-03-31 · by cgy4ever · Graph Theory
Problem Statement
Problem Statement
You may have already heard about the concept of "Six Degrees of Separation".
It means the following:
Imagine a graph where each person on Earth is a vertex, and two people are connected by an edge if they know each other.
Then, for any two vertices in this graph their distance should be at most 6.
Formally, we say that a graph has six degrees of separation if the above property is true for all pairs of its vertices.
Fox Ciel just made a similar graph for foxes. There are n foxes, numbered from 0 to n-1. You are given theint n and two int[] s a and b that describe the edges of the graph.
For each valid i, the foxes a[i] and b[i] know each other.
It is guaranteed that the given graph is simple - i.e., each pair contains two distinct foxes, and each unordered pair of foxes who know each other is only listed once.
Ciel's graph is also guaranteed to be connected, but it does not necessarily have six degrees of separation, as foxes are more solitary than humans. Your task is to add some (possibly none) edges to the graph to make it have six degrees of separation. The new graph must again be simple. You may add at most n / 3 new edges.
Return aint[] of the form {x0, y0, x1, y1, x2, y2, ...}, where (x0, y0), (x1, y1), (x2, y2) ... are the edges you want to add.
It is guaranteed that a valid solution always exists.
If there are multiple valid solutions, you may return any of them.
Note that you do not have to minimize the number of added edges.
Formally, we say that a graph has six degrees of separation if the above property is true for all pairs of its vertices.
Fox Ciel just made a similar graph for foxes. There are n foxes, numbered from 0 to n-1. You are given the
Ciel's graph is also guaranteed to be connected, but it does not necessarily have six degrees of separation, as foxes are more solitary than humans. Your task is to add some (possibly none) edges to the graph to make it have six degrees of separation. The new graph must again be simple. You may add at most n / 3 new edges.
Return a
Constraints
- n will be between 2 and 2,000, inclusive.
- a will contain between n-1 and 2,000 elements, inclusive.
- a and b will contain the same number of elements.
- Each element in a will be between 0 and n-1, inclusive.
- Each element in b will be between 0 and n-1, inclusive.
- The graph described by a and b will be simple.
- The graph described by a and b will be connected.
Examples
0)
3
{0,1,2}
{1,2,0}
Returns: { }
There are only 3 foxes and the distance between every pair is 1, so we don't need to add any edges.
1)
8
{0,1,2,3,4,5,6}
{1,2,3,4,5,6,7}
Returns: {0, 7 }
This time the distance between 0 and 7 is 7, so we need to add edges.
2)
12
{0,1,2,3,4,5,6,7,8,9,10,11}
{1,2,3,4,5,6,7,8,9,10,11,0}
Returns: { }
3)
13
{0,1,2,3,4,5,5,1,8,9,10,11}
{1,2,3,4,5,6,7,8,9,10,11,12}
Returns: {2, 9, 2, 5, 5, 9 }
4)
4
{0,0,0,1,1,2}
{1,2,3,2,3,3}
Returns: { }
Submissions are judged against all 210 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SixDegreesOfSeparation with a public method vector<int> getAdditionalEdges(int n, vector<int> a, vector<int> b) · 210 test cases · 2 s / 256 MB per case