Largest Component Size by Common Factor in C++
An understandable approach using C++ : map all the elements with its factors, so mapping process would take o(n*sqrt(n)) for all the elements. Then iterate thro
An understandable approach using C++ : map all the elements with its factors, so mapping process would take o(n*sqrt(n)) for all the elements. Then iterate through map and connect consecutive elements under a key, except  key=1.Then apply dfs for rest of the process.\n```\nclass Solution {\n    void fac(map <int,vector<int> > &mp,int a,int p){\n        for(int i=1;i<=sqrt(a);i++){\n            if(a%i==0){\n                if(a/i==i)\n                    mp[i].push_back(p);\n                else \n                {\n                    mp[i].push_back(p);\n                    mp[a/i].push_back(p);\n                }\n            }\n        }\n    }\n    void print(vector < vector<int> > &v){\n        \n        for(int i=0;i<v.size();i++){\n            cout<<i<<" : ";\n            for(int k=0;k<v[i].size();k++)\n                 cout<<v[i][k]<<" ";\n            cout<<endl;\n        }\n    }\n    void dfs(vector <vector<int> > &g, vector<bool>&b,int s,int &t){\n        stack <int> st;\n        st.push(s);\n        \n        while(!st.empty()){\n            int x=st.top();\n            st.pop();\n            if(b[x]==0){\n                b[x]=1;\n                t++;\n                for(int j=0;j<g[x].size();j++){\n                    if(b[g[x][j]]==0)\n                        st.push(g[x][j]);\n                        \n                }\n            }\n        }\n            \n    }\npublic:\n    int largestComponentSize(vector<int>& A) {\n        \n        map<int, vector<int> > mp;\n        for(int i=0;i<A.size();i++){\n            fac(mp,A[i],i);\n        }\n       \n        vector < vector<int> > g(A.size());\n        for(auto u : mp){\n            if(u.second.size()>1 && u.first!=1){\n                for(int i=0;i<u.second.size()-1;i++){\n                    g[u.second[i]].push_back(u.second[i+1]);\n                    g[u.second[i+1]].push_back(u.second[i]);\n                }\n            }\n        }\n        \n        //print(g);\n        \n        int mc=1;\n        vector <bool> b(A.size(),0);\n        for(int j=0;j<b.size();j++){\n            if(b[j]==0){\n                int t=0;\n                dfs(g,b,j,t);\n                mc=max(mc,t);\n                \n            }\n        }\n        return mc;\n        \n        \n        \n    }\n};\n```
[]