HackerRank : Week of Code 28 – The Value of Friendship

By | January 13, 2017
The Value of Friendship

Source : Hackerrank

You’re researching friendships between groups of n new college students where each student is distinctly numbered from 1 to n . At the beginning of the semester, no student knew any other student; instead, they met and formed individual friendships as the semester went on. The friendships between students are:

  • Bidirectional. If student a is friends with student b, then student b is also friends with student a.
  • Transitive. If student a  is friends with student b and student b is friends with student c, then student a is friends with student c. In other words, two students are considered to be friends even if they are only indirectly linked through a network of mutual (i.e., directly connected) friends.

The purpose of your research is to find the maximum total value of a group’s friendships, denoted by total. Each time a direct friendship forms between two students, you sum the number of friends that each of the n students has and add the sum to total.

You are given q queries, where each query is in the form of an unordered list of m distinct direct friendships between n students. For each query, find the maximum value of total among all possible orderings of formed friendships and print it on a new line.

Input Format

The first line contains an integer, q , denoting the number of queries. The subsequent lines describe each query in the following format:

  1. The first line contains two space-separated integers describing the respective values of n (the number of students) and m (the number of distinct direct friendships).
  2. Each of the m subsequent lines contains two space-separated integers describing the respective values of x and y (where x!=y ) describing a friendship between student x and student y.

Output Format

For each query, print the maximum value of total on a new line.

Sample Input 0

1
5 4
1 2
3 2
4 2
4 3

Sample Output 0

32

Explanation 0

image

The value of total  is maximal if the students form the m=4 direct friendships in the following order:

  1. Students 1 and 2 become friends:
    imageWe then sum the number of friends that each student has to get 1+1+0+0+0=2 .
  2. Students 2 and 4 become friends:
    imageWe then sum the number of friends that each student has to get 2+2+0+2+0=6
  3. Students 3  and 4 become friends:
    imageWe then sum the number of friends that each student has to get 3+3+3+3+0=12
  4. Students 3 and 2 become friends:
    imageWe then sum the number of friends that each student has to get 3+3+3+3+0=12 .

When we add the sums from each step, we get total = 2+6+12+12=32. We then print 32 on a new line.

Solution

Working on the solution.