Created
January 19, 2017 23:37
-
-
Save jianminchen/345a935aced6222ed72d5aa2a5378f18 to your computer and use it in GitHub Desktop.
Hackerrank week of code 28 - study code -
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#if DEBUG | |
using Microsoft.VisualStudio.TestTools.UnitTesting; | |
#endif | |
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
namespace ConsoleApplication1 | |
{ | |
class Program | |
{ | |
static void Main(string[] args) | |
{ | |
var t = Int32.Parse(Console.ReadLine()); | |
while (t > 0) | |
{ | |
var s = Console.ReadLine().Split(); | |
var n = Int32.Parse(s[0]); | |
var m = Int32.Parse(s[1]); | |
var friendShips = new List<Tuple<int, int>>(); | |
for (int i = 0; i < m; i++) | |
{ | |
s = Console.ReadLine().Split(); | |
friendShips.Add(new Tuple<int, int>(Int32.Parse(s[0]), Int32.Parse(s[1]))); | |
} | |
Console.WriteLine(GetAns(n, friendShips)); | |
t--; | |
} | |
} | |
public static long GetAns(int n, List<Tuple<int, int>> friends) | |
{ | |
long ret = 0; | |
var unionFind = new UnionFind(); | |
var relationCreatingClosedLoopNum = 0; | |
foreach (var f in friends) | |
{ | |
if (unionFind.IsSameGroup(f.Item1, f.Item2)) | |
{ | |
relationCreatingClosedLoopNum++; | |
continue; | |
} | |
unionFind.Unite(f.Item1, f.Item2); | |
} | |
var groups = unionFind.GetGroups().Where(v => v != 0).Select(v => v + 1).ToList(); | |
groups.Sort(); | |
groups.Reverse(); | |
long currentVal = 0; | |
foreach (var g in groups) | |
{ | |
currentVal += g * (g - 1); | |
} | |
ret = currentVal; | |
ret += currentVal * relationCreatingClosedLoopNum; | |
while (groups.Count() > 0) | |
{ | |
var num = groups.Last(); | |
groups.RemoveAt(groups.Count() - 1); | |
currentVal = 0; | |
foreach (var g in groups) | |
{ | |
currentVal += g * (g - 1); | |
} | |
ret += currentVal * (num - 1); | |
num--; | |
while (num > 1) | |
{ | |
ret += num * (num - 1); | |
num--; | |
} | |
} | |
return ret; | |
} | |
} | |
public class UnionFind | |
{ | |
private class Node | |
{ | |
public Node Parent { get; set; } | |
public int Rank { get; set; } | |
public HashSet<Node> Children; | |
public Node() | |
{ | |
Children = new HashSet<Node>(); | |
} | |
} | |
private Dictionary<object, Node> _dict = new Dictionary<object, Node>(); | |
private Node Root(object data) | |
{ | |
if (!_dict.ContainsKey(data)) | |
{ | |
var node = new Node(); | |
_dict.Add(data, node); | |
return node; | |
} | |
else | |
{ | |
var node = _dict[data]; | |
return Find(node); | |
} | |
} | |
private Node Find(Node node) | |
{ | |
if (node.Parent == null) return node; | |
return node.Parent = Find(node.Parent); | |
} | |
public void Unite(IComparable x, IComparable y) | |
{ | |
var xRoot = Root(x); | |
var yRoot = Root(y); | |
if (xRoot == yRoot) return; | |
if (xRoot.Rank < yRoot.Rank) | |
{ | |
ChangeParent(yRoot, xRoot); | |
} | |
else | |
{ | |
ChangeParent(xRoot, yRoot); | |
if (xRoot.Rank == yRoot.Rank) xRoot.Rank++; | |
} | |
} | |
void ChangeParent(Node parent, Node childRoot) | |
{ | |
if (childRoot.Parent != null) childRoot.Parent.Children.Remove(childRoot); | |
childRoot.Parent = parent; | |
childRoot.Parent.Children.Add(childRoot); | |
foreach (var child in childRoot.Children.ToList()) | |
{ | |
ChangeParent(parent, child); | |
} | |
} | |
public bool IsSameGroup(IComparable x, IComparable y) | |
{ | |
return Root(x) == Root(y); | |
} | |
public List<long> GetGroups() | |
{ | |
var ret = new List<long>(); | |
foreach (var r in _dict.Values.Where(d => d.Parent == null)) | |
{ | |
ret.Add(r.Children.Count()); | |
} | |
return ret; | |
} | |
} | |
#if DEBUG | |
[TestClass] | |
public class Test | |
{ | |
[TestMethod] | |
public void Tests() | |
{ | |
// sample case => 32 | |
//1 | |
//5 4 | |
//1 2 | |
//3 2 | |
//4 2 | |
//4 3 | |
// 12 -> 12 -> 6 -> 2 | |
var n = 5; | |
var m = 4; | |
var friends = new List<Tuple<int, int>> | |
{ | |
new Tuple<int, int>(1, 2), | |
new Tuple<int, int>(3, 2), | |
new Tuple<int, int>(4, 2), | |
new Tuple<int, int>(4, 3), | |
}; | |
Assert.AreEqual(32, Program.GetAns(n, friends)); | |
n = 7; | |
m = 7; | |
friends = new List<Tuple<int, int>> | |
{ | |
new Tuple<int, int>(1, 2), | |
new Tuple<int, int>(3, 2), | |
new Tuple<int, int>(3, 4), | |
new Tuple<int, int>(4, 2), | |
new Tuple<int, int>(1, 4), | |
new Tuple<int, int>(5, 6), | |
new Tuple<int, int>(5, 7), | |
}; | |
Assert.AreEqual(88, Program.GetAns(n, friends)); | |
} | |
[TestMethod] | |
public void RandomTest() | |
{ | |
var rnd = new Random(); | |
//var n = rnd.Next() % 100000 + 1; | |
var n = 100000; | |
var m = Math.Min(n * (n-1) / 2, 200000); | |
var friends = new List<Tuple<int, int>>(); | |
for (int i = 0; i < m; i++) | |
{ | |
friends.Add(new Tuple<int, int>(rnd.Next() % n + 1, rnd.Next() % n + 1)); | |
} | |
var result = Program.GetAns(n, friends); | |
Assert.IsTrue(true); | |
} | |
} | |
#endif | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment