C++ union find solution
We will only traverse the following part of the grid for efficiency:\n| 0 | * | * | * | * |\n| 0 | 0 | * | * | * |\n| 0 | 0 | 0 | * | * |\n| 0 | 0 | 0 | 0 | * |
We will only traverse the following part of the grid for efficiency:\n| 0 | * | * | * | * |\n| 0 | 0 | * | * | * |\n| 0 | 0 | 0 | * | * |\n| 0 | 0 | 0 | 0 | * |\n| 0 | 0 | 0 | 0 | 0 |\n\nThe diagonal elements are friends of themselves so we can ignore them, we are only concerned with distinct elements.\nAnd since M[i][j] = M[j][i] we don\'t need to traverse the other half.\n\nThen apply union and find operations sequentially on the desired part.\n\n```\nclass Solution {\npublic:\n    vector<int> friends;\n    \n    int find_friend(int i) {\n        if(friends[i] == i)\n            return i;\n        return friends[i] = find_friend(friends[i]);\n    }\n    \n    void union_friends(int i, int j) {\n        i = find_friend(i);\n        j = find_friend(j);\n        \n        if(i!=j)\n            friends[j] = i;\n    }\n    \n    int findCircleNum(vector<vector<int>>& M) {\n        int n = M.size();\n        int groups=0;\n        friends.resize(n);\n\n        for(int i=0;i<n;i++)\n            friends[i] = i;\n        \n        //Since each friend is initially friend to himself (M[i][i]),\n        //We will traverse only in the top right half of grid\n        //Since the bottom left half is the copy of it.\n        \n        for(int i=0;i<n;i++) {\n            for(int j=i+1;j<n;j++) {\n                if(M[i][j] == 1)\n                    union_friends(i,j);\n            }\n        }\n        \n        for(int i=0;i<n;i++) {\n            if(friends[i] == i)\n                groups++;\n        }\n        \n        return groups;\n    }\n};
['Union Find', 'C']