i was trying to solve this problem without creating a graph, i’ve found this code with a short explanation but i really can’t understand it. here’s the code and the explanation:
#include <bits/stdc++.h>
using namespace std;
/*
Store which gifts can be exchanged for what gifts using the solve method. For any cow that receives
a particular gift, we know that all gifts that appear before that gift in the preference list can be exchanged
for that cow's gift. We then realize that if a gift x can be switched with another cow's gift y, then whatever
y can be exchanged for can also be exchanged for x and so on. Solve recurses through all these
possibilities, and makes sure we visit everything a max of one time.
Then, we simply look through each cow's preference list and the first one that it can exchange for is
the best one. We also have to make sure that we don't check beyond the gift that it got.
*/
bool dp[500][500], proc[500];
int pref[500][500], N;
void solve(int P, int V) {
proc[P] = true;
for (int i = 0; pref[P][i] != P; i++) {
dp[pref[P][i]][V] = true;
if (!proc[pref[P][i]])
solve(pref[P][i], V);
}
}
int main() {
cin >> N;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++) {
cin >> pref[i][j];
pref[i][j]--;
}
for (int i = 0; i < N; i++) {
fill(proc, proc + N, false);
solve(i, i);
}
for (int i = 0; i < N; i++) {
int j;
for (j = 0; pref[i][j] != i; j++)
if (dp[i][pref[i][j]])
break;
cout << pref[i][j] + 1 << '\n';
}
}
this is the part of the explanation that i don’t understand: “all gifts that appear before that gift in the preference list can be exchanged for that cow’s gift. We then realize that if a gift x can be switched with another cow’s gift y, then whatever y can be exchanged for can also be exchanged for x and so on”