[Javascript] Optimal Hungarian Algorithm in O(m*m*n)
Intuition:\n\nThis may strike one as a bipartite graph problem, where the nodes of the left part are the students and the nodes of the right part are the mentor
**Intuition**:\n\nThis may strike one as a bipartite graph problem, where the nodes of the left part are the students and the nodes of the right part are the mentors. Each node on the left is connected with every node on the right, with a cost equal to the count of the same answers for the student and each mentor respectively. Essentially we want to make an assignment such that the total cost is maximized. This is known as the assignment problem, and the fastest way of solving such a problem is the Kuhn Munkres algorithm, better known as the Hungarian algorithm. There are a ton of resources online for studying the Hungarian algorithm but I am not going to delve into its theory here, as it\'s quite lengthy. \n\nIn any way, the assignment problem can be solved with easier ( yet less optimal complexity-wise) algorithms like Ford Fulkerson, and Hopcroft Karp.\n\n**Process**\n\nI first create an adjacency list between the students and the mentors, where A[i][j]= - (the count of the same answers of student i and mentor j).\nThe assignment problem is used to minimize the total cost, so in order to maximize it I need the edges to be negative.\nI then execute the Hungarian algorithm and return the negative result. \n```\nlet HunFast=(GRAPH)=>{\n    let a=[...Array(GRAPH.length)].map((d,i)=>[...GRAPH[i]])\n    let A=(len)=>[...Array(len)].map(d=>0)\n    a.unshift(A(a[0].length))\n    for(let i=0;i< a.length;i++)\n        a[i].unshift(0)\n    let n=a.length-1,m=a[0].length-1,u=A(n+1), v=A(m+1), p=A(m+1), way=A(m+1);\n    for (let i=1; i<=n; i++) {\n        p[0] = i;\n        var j0 = 0,minv=A(m+1).map(d=>Infinity),used=A(m+1).map(d=>false)\n        do {\n            used[j0] = true;\n            var i0 = p[j0] ,  delta = Infinity,  j1;\n            for (let j=1; j<=m;j++)\n                if (!used[j]) {\n                    let cur = a[i0][j]-u[i0]-v[j];\n                    if (cur < minv[j])\n                        minv[j] = cur,  way[j] = j0;\n                    if (minv[j] < delta)\n                        delta = minv[j],  j1 = j;\n                }\n            for (let j=0; j<=m;j++)\n                if (used[j])\n                    u[p[j]] += delta,  v[j] -= delta;\n                else\n                    minv[j] -= delta;\n            j0 = j1;\n        } while (p[j0] != 0);\n        do {\n            let j1 = way[j0];\n            p[j0] = p[j1],j0 = j1\n        } while (j0);\n    }\n    return -v[0]\n}\nvar maxCompatibilitySum = function(S, M) {\n    let m=S.length, A=[...Array(m)].map(d=>[...Array(m)])\n    for(let i=0;i<m;i++ )\n        for(let j=0;j<m;j++)\n            A[i][j]=-S[i].reduce((a,c,k)=> a+ Number(c===M[j][k]),0)\n    return -HunFast(A)\n};\n\n```
['Graph', 'JavaScript']