Skip to content

Instantly share code, notes, and snippets.

@mat3u
Created Jun 29, 2015
Embed
What would you like to do?
using System.Collections.Generic;
using System.Linq;
namespace MergeLinks
{
public class Disjoint<T>
{
private readonly Dictionary<int, HashSet<T>> _groups;
private int _lastGroupKey = 0;
public Disjoint()
{
_groups = new Dictionary<int, HashSet<T>>();
}
public IEnumerable<IEnumerable<T>> Groups
{
get {
return _groups.Select(@group => @group.Value);
}
}
public void Add(T a, T b)
{
var aRoot = Find(a);
var bRoot = Find(b);
if (aRoot.HasValue && !bRoot.HasValue)
{
AddToExisting(b, aRoot.Value);
}
else if (!aRoot.HasValue && bRoot.HasValue)
{
AddToExisting(a, bRoot.Value);
}
else if (aRoot.HasValue && bRoot.HasValue && aRoot.Value != bRoot.Value)
{
Union(aRoot.Value, bRoot.Value);
}
else if (!aRoot.HasValue && !bRoot.HasValue)
{
var @new = AddToNew(a);
AddToExisting(b, @new);
}
else /* aRoot.Value == bRoot.Value */
{
// Do nothing!
}
}
private void Union(int aRoot, int bRoot)
{
foreach (var elem in _groups[bRoot])
{
_groups[aRoot].Add(elem);
}
_groups.Remove(bRoot);
}
private void AddToExisting(T b, int parent)
{
_groups[parent].Add(b);
}
private int AddToNew(T b)
{
var newGroupKey = _lastGroupKey;
_groups.Add(newGroupKey, new HashSet<T>() { b });
_lastGroupKey = newGroupKey + 1;
return newGroupKey;
}
public int? Find(T elem)
{
foreach (var @group in _groups.Where(@group => @group.Value.Contains(elem)))
{
return @group.Key;
}
return null;
}
}
}
using System.IO;
using System.Linq;
namespace MergeLinks
{
class Program
{
static void Main(string[] args)
{
var ds = new Disjoint<int>();
using (var tr = File.OpenText(args[0]))
{
int progress = 0;
while (!tr.EndOfStream)
{
var line = tr.ReadLine();
var segments = line.Split('\t').Select(int.Parse).ToList();
ds.Add(segments[0], segments[1]);
Console.Write("\r{0}", progress++);
}
}
int num = 1;
foreach (var @group in ds.Groups)
{
Console.WriteLine("{0}. {1}", num++, string.Join(",", @group));
}
Console.ReadKey();
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment