Disjoint set c# 구현

(3) Explore - LeetCode

Account Login - LeetCode

 

Program.cs

static void Main(string[] args)
{
    Disjoint dj = new Disjoint();

    List<Union> unions = new List<Union>();
    unions.Add(new Union(0, 1));
    unions.Add(new Union(0, 2));
    unions.Add(new Union(1, 3));
    unions.Add(new Union(4, 8));
    unions.Add(new Union(5, 6));
    unions.Add(new Union(5, 7));
    unions.Add(new Union(9));

    int parent = dj.findParent(3, unions);
    Console.WriteLine($"Vertex 3 is {parent}");

    parent = dj.findParent(2, unions);
    Console.WriteLine($"Vertex 2 is {parent}");

    parent = dj.findParent(8, unions);
    Console.WriteLine($"Vertex 8 is {parent}");

    parent = dj.findParent(6, unions);
    Console.WriteLine($"Vertex 6 is {parent}");

    parent = dj.findParent(7, unions);
    Console.WriteLine($"Vertex 7 is {parent}");

    parent = dj.findParent(9, unions);
    Console.WriteLine($"Vertex 9 is {parent}");

    bool connected = dj.isConnected(0, 3);
    Console.WriteLine($"Vertex 0 and 3 connected? {connected}");

    connected = dj.isConnected(4, 5);
    Console.WriteLine($"Vertex 4 and 5 connected? {connected}");
}

DisJoint.cs

namespace Algorithm.Graph
{
    class Disjoint
    {

        public List<int> array { get; set; }

        public int findParent(int num, List<Union> unions)
        {
            initArray(unions);

            int parent = array[num];
            realParent(parent);
       
            return realParent(parent);
        }

        public bool isConnected(int parent, int root)
        {
            if (realParent(root, parent) == parent)
                return true;
            else return false;
        }


        public int realParent(int idx)
        {
            if (idx == array[idx])
                return array[idx];

            return realParent(array[idx]);
        }

        public int realParent(int idx, int standard)
        {
            if (array[idx] == standard)
                return array[idx];

            if (array[idx] == idx)
                return Constants.NOK;

            return realParent(array[idx], standard);
        }

        public void initArray(List<Union> unions)
        {
            array = new List<int>();

            int cnt = Constants.NOK;

            foreach (Union u in unions)
            {
                if (cnt < u.root)
                    cnt = u.root;

                if (cnt < u.parent)
                    cnt = u.parent;
            }

            for (int i = 0; i <= cnt; ++i)
            {
                array.Add(i);
            }

            foreach (Union u in unions)
            {
                int idx = u.root;
                int val = u.parent;
                if (u.root == Constants.NOK)
                    continue;

                array[idx] = val;
            }
        }
    }
}

Union.cs

namespace Algorithm.Graph
{
    class Union
    {
        public int parent { get; set; }
        public int root { get; set; }

        public Union(int num1, int num2)
        {
            this.parent = num1;
            this.root   = num2;
        }

        public Union(int num1)
        {
            this.parent = num1;
            this.root   = Constants.NOK;
        }
    }
}

 

결과