[C#] Union Find - Every line explained
Idea is to have multiple sets for each factor i.e. one set which has all numbers divisible by 2, one set with all numbers divisible by 3 etc.\n Once we encounte
* Idea is to have multiple sets for each factor i.e. one set which has all numbers divisible by 2, one set with all numbers divisible by 3 etc.\n* Once we encounter any number which is divisible by say 2 and 3, we join the two sets (i.e. set for factor 2 and set for factor 3)\n* At the end we return the set with max numbers in it.\n```\npublic class Solution {\n    Dictionary<int, int> dict = new Dictionary<int, int>(); // key is the factor, value is index of first num with that factor\n    UnionFind uf;                                           // unionfind will maintain multiple sets for each factor\n    public int LargestComponentSize(int[] nums) {\n        var n = nums.Length;\n        uf = new UnionFind(n);\n        \n        for (int i = 0; i < n; i++){                    // for each number in input array\n            var num = nums[i];                          // the current number we are processing\n            StartNewSetOrJoin(num, i, num);             // the number is a factor of itself\n            for (int j = 2; j*j <= num; j++){           // j*j <= num because we want to only check factors till square root of num\n                if (num % j == 0){                      // if j is a factor of num\n                    StartNewSetOrJoin(num, i, j);       // add current num to set of factor j\n                    StartNewSetOrJoin(num, i, num/j);   // obviously num/j is also a factor of num \n                }\n            }\n        }\n        \n        return uf.max;\n    }\n    \n    private void StartNewSetOrJoin(int num, int numIdx, int factor){\n        if (!dict.ContainsKey(factor)){         // no number has had this factor yet\n            dict[factor] = numIdx;              // so a new set starts with current number\n        }else{                                  // if there is already a set with current factor as parent\n            uf.Union(numIdx, dict[factor]);     // join current number with that set\n        }\n    }\n}\n\n\npublic class UnionFind{\n    int[] parent;                           // it stores index of first node in a set\n    int[] size;                             // keeps track of size of a set\n    public int max;                         // this we maintain so that we don\'t have to do a loop later to get biggest set\n    \n    public UnionFind(int n){\n        parent = new int[n];\n        size = new int[n];\n        max = 1;                            // all disjoint sets have one node\n        for(int i=0; i<n; i++){\n            parent[i] = i;                  // all are self parent initially\n            size[i] = 1;                    // size of all disjoint sets is 1 initially\n        }\n    }\n    \n    public int Find(int n){\n        if(parent[n] != n)                  // if there are multiple nodes in current set\n            parent[n] = Find(parent[n]);    // find parent node of the set\n        return parent[n];                   // and then return the parent\n    }\n    \n    public void Union(int n1, int n2){\n        var n1_p = Find(n1);                // find parent of number 1\n        var n2_p = Find(n2);                // find parent of number 2\n        if(n1_p != n2_p){                   // if parent of number 1 and number 2 are not same, then we need to join two sets\n            parent[n1_p] = n2_p;            // make n2\'s parent as common parent for both sets. ideally smaller set should update its parent\n            size[n2_p] += size[n1_p];       // update size of the merged set\n            max = Math.Max(max, size[n2_p]);// update the max size of any set\n        }\n        \n    }\n}\n```
['Union Find']