JoinAClub
SRM 810 · 2021-07-22 · by misof
Problem Statement
A school club is formed as follows:
- First, someone becomes the founder of a club and its only member.
- Then, zero or more times, a member of the club invites one of their friends to join the club.
There are N kids. They are numbered from 0 to N-1, inclusive.
You are given a list of all friendships: for each valid i, kids X[i] and Y[i] are friends.
Compute the size S of the largest possible club. Then, find one order in which some kids can form that club.
Return a
Constraints
- N will be between 1 and 50, inclusive.
- X will have between 0 and 250 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 i, X[i] will not be equal to Y[i].
- All unordered pairs of kids described by X and Y will be distinct.
5
{}
{}
Returns: {2 }
Nobody has any friends, so the biggest possible club consists only of its founder.
4
{0, 0, 0, 1, 1, 3}
{1, 2, 3, 3, 2, 2}
Returns: {2, 0, 1, 3 }
Four kids, everyone is friends with everyone else. All four of them can form a club and any order in which they join is valid.
6
{0, 1, 2, 5}
{3, 3, 3, 3}
Returns: {2, 3, 0, 1, 5 }
In the example output 2 is the club's founder, then 2 invites 3, and then 3 invites 0, 1, and 5.
47
{0, 4, 6, 6, 42}
{13, 7, 7, 23, 15}
Returns: {4, 7, 6, 23 }
47
{0, 14, 6, 6, 42}
{13, 7, 7, 23, 15}
Returns: {6, 7, 23, 14 }
Submissions are judged against all 80 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class JoinAClub with a public method vector<int> maximumClub(int N, vector<int> X, vector<int> Y) · 80 test cases · 2 s / 256 MB per case