using System;
using System.Collections.Generic;
using System.Linq;

public class GroupedSet<T>
{
    // Intern houdt elk element een verwijzing naar de bijbehorende groep bij
    private readonly Dictionary<T, HashSet<T>> _groups = new();

    /// <summary>
    /// Voegt een relatie toe tussen twee items. Als ze nog niet bestaan,
    /// worden ze aan een nieuwe groep toegevoegd. Als ze in verschillende
    /// groepen zitten, worden de groepen samengevoegd.
    /// </summary>
    public void AddRelation(T a, T b)
    {
        _groups.TryGetValue(a, out var setA);
        _groups.TryGetValue(b, out var setB);

        if (setA == null && setB == null)
        {
            var newSet = new HashSet<T> { a, b };
            _groups[a] = newSet;
            _groups[b] = newSet;
        }
        else if (setA != null && setB == null)
        {
            setA.Add(b);
            _groups[b] = setA;
        }
        else if (setA == null && setB != null)
        {
            setB.Add(a);
            _groups[a] = setB;
        }
        else if (!ReferenceEquals(setA, setB))
        {
            // Merge twee bestaande sets
            setA.UnionWith(setB);
            foreach (var item in setB)
                _groups[item] = setA;
        }
    }

    /// <summary>
    /// Haalt de groep op waarin een item zich bevindt.
    /// </summary>
    public HashSet<T>? GetGroup(T item)
    {
        return _groups.TryGetValue(item, out var set) ? set : null;
    }

    /// <summary>
    /// Controleert of twee items in dezelfde groep zitten.
    /// </summary>
    public bool AreConnected(T a, T b)
    {
        return GetGroup(a) != null && ReferenceEquals(GetGroup(a), GetGroup(b));
    }

    /// <summary>
    /// Geeft alle unieke groepen terug.
    /// </summary>
    public IEnumerable<HashSet<T>> GetAllGroups()
    {
        return _groups.Values.Distinct(ReferenceEqualityComparer<HashSet<T>>.Instance);
    }

    /// <summary>
    /// Verwijdert een element (en eventueel de hele groep als die leeg is).
    /// </summary>
    public void Remove(T item)
    {
        if (!_groups.TryGetValue(item, out var set))
            return;

        set.Remove(item);
        _groups.Remove(item);

        if (set.Count == 0)
            return;

        // Werk dictionary bij om lege verwijzingen te verwijderen
        foreach (var i in set)
            _groups[i] = set;
    }

    /// <summary>
    /// Leegt alle groepen.
    /// </summary>
    public void Clear()
    {
        _groups.Clear();
    }
}

/// <summary>
/// Hulpfunctie om distinct op referenties te doen.
/// </summary>
public class ReferenceEqualityComparer<T> : IEqualityComparer<T>
    where T : class
{
    public static readonly ReferenceEqualityComparer<T> Instance = new();
    public bool Equals(T? x, T? y) => ReferenceEquals(x, y);
    public int GetHashCode(T obj) => System.Runtime.CompilerServices.RuntimeHelpers.GetHashCode(obj);
}