Simple C++ Solution || Fully Explained at begineers level || Easy Understanding of UNION concept
TOPIC: UNION FIND\n   NOT A BIG TASK :), JUST GO LINE BY LINE \n\n       In union we just make any element leader of any group and make other elements as a grou
**TOPIC: UNION FIND\n   NOT A BIG TASK :), JUST GO LINE BY LINE** \n\n       In union we just make any element leader of any group and make other elements as a group member.\n\n**Let\'s say 1 and 2 are friend , and 2 and 3 are also friend \nThen indirectly 1 and 3 are also friends. We can say that 1,2,3 are in same group.**\n\nHow we will deal with it in UNION:\n\nWE have given **n * n matrix** , then **maximum number of group will be n**, if nobody is friend of none.\n\nLets Say n=5\nNow we mark all of them initially with -1, because at starting all are alone, all are self leader.\n**At the end we will find -1 for those index which will be leader of any group**\n\n _INDEX :     **[ 1 ,  2 ,3 ,4 ,   5]**\nVALUES: **[-1,-1,-1,-1,-1]**\n\nNow **1 is friend of 2**, mark **2** as a leader , how can we do this, simple ,**point index 2 from 1**\n _INDEX :     **[ 1 ,  2 ,3 ,4 ,   5]**\nVALUES: **[  2,-1,-1,-1, -1]**\nHere how we will find leader ,start from index 1\n\n**1 is pointing 2 , 1->2\n2 is pointing -1, 2 is leader of group**\n\n\nNow **2 is friend of 3**, Now **point 2 at index 3**\n _INDEX :     **[ 1 ,  2 ,3 ,4 ,   5]**\nVALUES: **[  2 , 3,-1,-1, -1]**\n\n**1 is pointing 2 , 1->2\n2 is pointing 3 , 2->3\n3 is pointing -1 , 3 is leader of group**\n\n\nNow if we start finding **leader of 1 and 2** , then **3** is the leader (**COMMON LEADER: SAME GROUP**)\n\nNow **4 is friend of 5**, Now **point 4 at index 5**\n _INDEX :     **[ 1 ,  2 ,3 ,4 ,   5]**\nVALUES: **[  2 , 3,-1, 5, -1]**\n\nAt the end just count total number of parent nodes whose value is -1.\nNow we have **two** groups **{1,2,3}** and **{4,5}** , NOW go to solution line by line :)\n \n```\nclass Solution {\npublic:\n    \n    //It will be use to store groups\n    vector<int> v;\n    \n    //Find the leader of any group in which x lies\n    //if not lie in any group then it is self leader\n    int parent(int x)\n    {\n        //self leader\n        if(v[x]==-1) return x; \n        //find the leader of self parent\n        return v[x]=parent(v[x]);\n    }\n    \n    //Adding 2 friends in a group\n    void _union(int a,int b)\n    {\n        //find the leader of both a and b\n        int p_a=parent(a),p_b=parent(b);\n        \n        //if already in same group, i.e leader of both of them are same then return\n        if(p_a==p_b) return; \n        /*\n         if both of them are from different group then add both the groups \n         and make a single common group\n         We can do this by -> leader of 1st group is member of 2nd group \n         and now main leader of whole group is leader of 2nd member\n        */ \n        v[p_a]=p_b; //v[p_a] will store the index of leader of whole group\n    }\n    \n    int findCircleNum(vector<vector<int>>& M) { \n        int n=M.size();\n        v=vector<int> (n,-1);//there will be maximum n group, mark all as a leader\n        \n        //making group\n        for(int i=0;i<n;i++)\n        {\n            for(int j=0;j<n;j++)\n            {\n                if(M[i][j])  //if i is friend of j, add them in a group\n                { \n                    //if i is in any group then add j in that group\n                    //or vice-versa\n                    _union(i,j);  //Add them in a group\n                }\n            }\n        }\n        int c=0; \n        \n        //counting group\n        for(int i=0;i<n;i++)\n        {\n            if(v[i]==-1) c++; //counting total number of parents\n        }\n        return c; \n    }\n};\n```\n\n***Time Complexity: O(N * N * log(N))\nSpace Complexity: O(N)***  \n\n**We are traversing N * N size matrix and finding parent each time in vector  of size N\nUsing a vector to store parent of size N**\n\n\n
['Union Find', 'C', 'C++']