Leetcode 547 - friend circle - disjoint set - path compression, recursive call to set the parent of node to the root of set.

Leetcode547_friendCircle_disjointSet.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode547_disjointset
{
    /// <summary>
    /// Leetcode 547 
    /// Friends circle 
    /// https://leetcode.com/problems/friend-circles/#/description
    /// Use disjoint set, union find algorithm
    /// </summary>
    class Program
    {
        static void Main(string[] args)
        {
        }

        static int[] disjointSet = new int[0];

        public static int FindCircleNum(int[,] M)
        {
            var rows = M.GetLength(0);
            if (rows == 0)
            {
                return 0;
            }

            disjointSet = new int[rows];

            for (int row = 0; row < rows; ++row)
            {
                disjointSet[row] = row;
            }

            for (int row = 0; row < rows; row++)
            {
                for (int col = row + 1; col < rows; col++)
                {
                    if (M[row, col] == 1)
                    {
                        merge(row, col);
                    }
                }
            }

            // calculate how many disjoint sets
            int count = 0;
            for (int i = 0; i < rows; ++i)
            {
                if (i == disjointSet[i])
                {
                    count++;
                }
            }

            return count;
        }

        private static void merge(int i, int j)
        {
            disjointSet[parent(i)] = parent(j);
        }

        /// <summary>
        /// code review 
        /// line 74 - it is recursive call and also path compression
        /// reset the node's parent to its root of disjoint set. 
        /// </summary>
        /// <param name="row"></param>
        /// <returns></returns>
        private static int parent(int row)
        {
            if (disjointSet[row] == row)
            {
                return row;
            }

            return disjointSet[row] = parent(disjointSet[row]); // path compression
        }
    } 
}