partitionasforestv2.cs

来自「Data Structures and Algorithms with Obj」· CS 代码 · 共 54 行

namespace Opus6
{
    using System;

    [Version("$Id: PartitionAsForestV2.cs,v 1.4 2001/10/28 19:50:09 brpreiss Exp $"), Copyright("Copyright (c) 2001 by Bruno R. Preiss, P.Eng.")]
    public class PartitionAsForestV2 : PartitionAsForest
    {
        public PartitionAsForestV2(int n) : base(n)
        {
        }

        public override Set Find(int item)
        {
            PartitionAsForest.PartitionTree tree3;
            PartitionAsForest.PartitionTree tree1 = base.array[item];
            while (tree1.parent != null)
            {
                tree1 = tree1.parent;
            }
            for (PartitionAsForest.PartitionTree tree2 = base.array[item]; tree2.parent != null; tree2 = tree3)
            {
                tree3 = tree2.parent;
                tree2.parent = tree1;
            }
            return tree1;
        }

        public override void Join(Set s, Set t)
        {
            PartitionAsForest.PartitionTree tree1 = (PartitionAsForest.PartitionTree) s;
            PartitionAsForest.PartitionTree tree2 = (PartitionAsForest.PartitionTree) t;
            this.CheckArguments(tree1, tree2);
            if (tree1.Count > tree2.Count)
            {
                tree2.parent = tree1;
                tree1.Count += tree2.Count;
            }
            else
            {
                tree1.parent = tree2;
                tree2.Count += tree1.Count;
            }
            base.count--;
        }

        public static void Main()
        {
            PartitionAsForest.TestPartition(new PartitionAsForestV2(5));
        }

    }
}