| 1 | vi stable_marriage(int n, int** m, int** w) { |
| 2 | queue<int> q; |
| 3 | vi at(n, 0), eng(n, -1), res(n, -1); vvi inv(n, vi(n)); |
| 4 | rep(i,0,n) rep(j,0,n) inv[i][w[i][j]] = j; |
| 5 | rep(i,0,n) q.push(i); |
| 6 | while (!q.empty()) { |
| 7 | int curm = q.front(); q.pop(); |
| 8 | for (int &i = at[curm]; i < n; i++) { |
| 9 | int curw = m[curm][i]; |
| 10 | if (eng[curw] == -1) { } |
| 11 | else if (inv[curw][curm] < inv[curw][eng[curw]]) |
| 12 | q.push(eng[curw]); |
| 13 | else continue; |
| 14 | res[eng[curw] = curm] = curw, ++i; break; } } |
| 15 | return res; } |
| 16 | // vim: cc=60 ts=2 sts=2 sw=2: |