You're researching friendships between groups \$n\$ of 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:
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). 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\$.
Constraints
1. 1 <= q <= 16
2. 1 <= n <= 100000
3. 1 <= m <= min(n(n-1)/2, 200000)
- 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
The value of \$total\$ is maximal if the students form the m = 4 direct friendships in the following order:
Students \$1\$ and \$2\$ become friends:
We then sum the number of friends that each student has to get 1 + 1 + 0 + 0 + 0 = 2.
Students \$2\$ and \$4\$ become friends:
We then sum the number of friends that each student has to get 2 + 2 + 0 + 2 + 0 = 6.
Students 3 and 4 become friends:
We then sum the number of friends that each student has to get 3 + 3 + 3 + 3 + 0 = 12.
Students 3 and 2 become friends:
We 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.
My introduction of algorithm
The algorithm is the hard one and also one of Hackerrank weekcode \$28\$ contest in January 2017, I spent a few hours in the contest to read the problem statement and also read all the discussion. I did some study on disjoint set, but I did not come out clear ideas how to divide groups, implement a graph. I learned through the discussion that the friendship should be added to maximize the value, and studied the test case in the following (5 nodes in the graph):
1. student 1 and 2 become friends
1-2 3 4 5, we then sum the number of friends that each student has
to get 1 + 1 + 0 + 0 + 0 = 2.
2. Student 2 and 3 become friends:
1-2-3 4 5, we then sum the number of friends that each student has to get
2 + 2 + 2 + 0 + 0 = 6.
3. Student 4 and 5 become friends:
1-2-3 4-5, we then sum the number of friends that each student has to get
2 + 2 + 2 + 1 + 1 = 8.
4. Student 1 and 3 become friends: (we hold to add 1 and 3 until 4 and 5 are added to maximize the value.)
1-2-3 4-5, we then sum the number of friends that each student has to get
2 + 2 + 2 + 1 + 1 = 8.
Total is 2 + 6 + 8 + 8 = 24.
If the friendship \$1\$ and \$3\$ are added before adding 4 and 5, then the value is less than \$24\$.
After the contest, I studied one of C# submission with maximum score, and then did some code review, tried to understand the graph design and also read the hackerrank editorial notes, understood the process to get maximum value of friendship. I put together C# code and also tested on hackerrank, the code passed all test cases. Please help me to review my C# code.
Hightlights of changes
Add name variable in the class GraphNode to help identify node; add the test case to help understand the algorithm, and be able to add comment to explain the function Connect; use meaningful variable names after code review. I already spent hours on the algorithm and really look forward to work hard on graph algorithm and be able to perform one graph algorithm in week of code contest in short future.
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
class Solution
{
public class Group
{
public int totalNumberNodes = 1;
}
/*
* GraphNode class
*/
public class GraphNode
{
/* Julia added the variable: name, so she can track GraphNode and
* work on the test case with 5 nodes: 0, 1, 2, 3, 4
*/
public string name;
// variables are defined by original author, study code from
// one of submissions with maximum score
public Group group;
public List<Edge> edges = new List<Edge>();
public GraphNode(string s)
{
this.name = s;
}
/*
* Work on the test case, illustrate the process using specific examples.
*
* Use name to track with edge, which node in the test case:
* 1-2-3 4-5
* 5 nodes in the graph, 4 connections, 1-3 is redundant.
*
* Go over each edge, and then remove friend node from nodes
* HashSet, edge from edges HashSet, and share the group to
* friend node, add one more to variable n, push friendNode
* to the stack.
*/
public void Connect(
HashSet<GraphNode> nodes,
HashSet<Edge> edges,
Stack<GraphNode> neighbours)
{
foreach (var edge in this.edges)
{
var friendNode = (edge.id_1 != this) ? edge.id_1 : edge.id_2;
if (friendNode.group == null)
{
nodes.Remove(friendNode);
edges.Remove(edge);
friendNode.group = group;
group.totalNumberNodes++;
neighbours.Push(friendNode);
}
}
}
}
public class Edge
{
public GraphNode id_1;
public GraphNode id_2;
}
static void Main(string[] args)
{
ProcessInput();
//RunSampleTestcase();
}
/*
* Need to work on the sample test case
* 1. student 1 and 2 become friends
* 1-2 3 4 5, we then sum the number of friends that each student has
* to get 1 + 1 + 0 + 0 + 0 = 2.
* 2. Student 2 and 3 become friends:
* 1-2-3 4 5, we then sum the number of friends that each student has to get
* 2 + 2 + 2 + 0 + 0 = 6.
* 3. Student 4 and 5 become friends:
* 1-2-3 4-5, we then sum the number of friends that each student has to get
* 2 + 2 + 2 + 1 + 1 = 8.
* 4. Student 1 and 3 become friends: (we hold to add 1 and 3 until 4 and 5
* are added to maximize the value.)
* 1-2-3 4-5, we then sum the number of friends that each student has to get
* 2 + 2 + 2 + 1 + 1 = 8.
* Total is 2 + 6 + 8 + 8 = 24.
*/
public static void RunSampleTestcase()
{
int queries = 1;
string[][] datas = new string[1][];
datas[0] = new string[2];
datas[0][0] = "5";
datas[0][1] = "4";
string[][] allFriendships = new string[1][];
allFriendships[0] = new string[4];
allFriendships[0][0] = "1 2";
allFriendships[0][1] = "2 3";
allFriendships[0][2] = "1 3";
allFriendships[0][3] = "4 5";
IList<long> result = MaximizeValues( queries, datas, allFriendships);
Debug.Assert(result[0] == 24);
}
/*
* code review:
* Everything is in one function, should break down a few of pieces
* 1. Input
* 2. Set up multiple graphes
* 3. minimum edges to connect the graph
* 4. extra edges to hold for maximum output, added by descending order.
* 4. Output
*/
public static void ProcessInput()
{
int queries = Convert.ToInt32(Console.ReadLine());
string[][] graphData = new string[queries][];
string[][] allFriendships = new string[queries][];
for (int query = 0; query < queries; query++)
{
string[] data = Console.ReadLine().Split(' ');
int totalNodes = Convert.ToInt32(data[0]);
int friendships = Convert.ToInt32(data[1]);
graphData[query] = new string[] { totalNodes.ToString(), friendships.ToString() };
allFriendships[query] = new string[friendships];
for (int i = 0; i < friendships; i++)
{
allFriendships[query][i] = Console.ReadLine();
}
} // end of process input
IList<long> result = MaximizeValues(queries, graphData, allFriendships);
foreach(long value in result)
{
Console.WriteLine(value);
}
}
/*
* Maximum value to add the friendship
* 3 rules to follow - check editorial notes:
* The graph is comprised of several components.
* Each component has its own size.
* 1. At first if a component has S nodes, you just need to add S - 1
* edges to make the component connected (a subtree of the component),
* add the rest of the edges at the end when all the components
* are connected in themselves.
* 2. At the end, when all of the components are connected, add
* the extra edges.
* 3. But what about the order of the components? Its better to
* add larger components first
* so that larger numbers are repeated more.
* 4. What about a component in itself? Try to make a tree from that component.
*/
public static IList<long> MaximizeValues(
int queries,
string[][] datas,
string[][] allFriendships)
{
IList<long> output = new List<long>();
for (int query = 0; query < queries; query++)
{
string[] data = datas[query];
int totalNodes = Convert.ToInt32(data[0]);
int friendships = Convert.ToInt32(data[1]);
var map = new GraphNode[totalNodes];
var nodes = new HashSet<GraphNode>();
for (int node = 0; node < totalNodes; node++)
{
map[node] = new GraphNode(node.ToString());
nodes.Add(map[node]);
}
var edges = new HashSet<Edge>();
var friendship = allFriendships[query];
for (int i = 0; i < friendships; i++)
{
string[] relationship = friendship[i].Split(' ');
var edge = new Edge();
edge.id_1 = map[Convert.ToInt32(relationship[0]) - 1];
edge.id_2 = map[Convert.ToInt32(relationship[1]) - 1];
edges.Add(edge);
edge.id_1.edges.Add(edge);
edge.id_2.edges.Add(edge);
}
// end of process input
var groups = new List<Group>();
// use stack - how to understand the stack's functionality here?
// write down something here - go over a test case to understand
// the code
while (nodes.Count > 0)
{
var node = nodes.First();
nodes.Remove(node);
groups.Add(node.group = new Group());
var neighbours = new Stack<GraphNode>();
node.Connect(nodes, edges, neighbours);
while (neighbours.Count > 0)
{
GraphNode current = neighbours.Pop();
current.Connect(nodes, edges, neighbours);
}
}
long result = 0;
long sum = 0;
foreach (var edge in groups.OrderByDescending(g => g.totalNumberNodes))
{
for (int i = 1; i < edge.totalNumberNodes; i++)
{
result += (i + 1) * (long)i + sum;
}
sum += (long)edge.totalNumberNodes * (edge.totalNumberNodes - 1);
}
output.Add(result + edges.Count * sum);
}
return output;
}
}
