Let's start by constructing a directed graph $G$ with vertices labeled $1\ldots N$ that contains an edge $i\to j$ if $i=j$ or cow $i$ prefers gift $j$ to gift $i$. For the sample case, $G$ would contain the following edges:

1 -> 1
2 -> 1
2 -> 3
2 -> 2
3 -> 1
3 -> 2
3 -> 3
4 -> 1
4 -> 2
4 -> 3
4 -> 4

There is a one-to-one correspondence between valid distributions and partitions of the vertices of $G$ into simple cycles. For example, assigning gift 1 to cow 1, gift 3 to cow 2, gift 2 to cow 3, and gift 4 to cow 4 would correspond to the following subset of $G$'s edges: $\{1\to 1, 2\to 3, 3\to 2, 4\to 4\}$. This subset of edges partitions the vertices of $G$ into three cycles: a self-loop involving $1$, a loop involving $2$ and $3$, and another self-loop involving $4$.

Observation 1: There is a distribution where cow $i$ receives gift $j$ if and only if $G$ has a simple cycle containing edge $i\to j$.

Proof:

Only If: A distribution where cow $i$ receives cow $j$ corresponds to a partition of the vertices of $G$ into some number of simple cycles containing the edge $i\to j$. It follows that one of those simple cycles contains the edge $i\to j$.

If: Suppose there exists a simple cycle $C$ containing $i\to j$. Then we can assign each cow along $C$ the gift originally given to the next cow along the cycle, and every cow along $C$ will end up strictly better off. Let all cows not along $C$ receive their original gifts. This corresponds to a valid distribution. $\blacksquare$

Observation 2: Using the first observation, $G$ has a simple cycle containing edge $i\to j$ if and only if there exists a path from $j$ to $i$.

Solution: In $\mathcal{O}(N^3)$ time, compute all pairs of vertices $(i,j)$ such that there exists a path from $i$ to $j$. In the code below, we set $\texttt{reachable}[i][j]=1$ if such a path exists. The most straightforward way to do this is to start a depth-first search from each $i$. Alternatively, we can use Floyd-Warshall with bitsets to shave a constant factor off the runtime.

After that, for each cow $i$, it remains to iterate over her preference list and output the first gift $g$ such that there exists a path from $g$ to $i$.

#include <bits/stdc++.h>
using namespace std;

int N;
bitset<501> reachable[501];
vector<int> gifts[501];

void dfs(int src, int cur) {
	if (reachable[src][cur])
		return;
	reachable[src][cur] = true;
	for (int g : gifts[cur])
		dfs(src, g);
}

void calc_reachable_dfs() {
	for (int i = 1; i <= N; ++i)
		dfs(i, i);
}

void calc_reachable_floyd() {
	for (int i = 1; i <= N; ++i)
		for (int g : gifts[i])
			reachable[i][g] = true;
	for (int k = 1; k <= N; ++k) // run floyd-warshall
		for (int i = 1; i <= N; ++i)
			if (reachable[i][k])
				reachable[i] |= reachable[k];
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> N;
	assert(N <= 500);
	for (int i = 1; i <= N; ++i) {
		gifts[i].resize(N);
		for (int &g : gifts[i])
			cin >> g;
		while (gifts[i].back() != i)
			gifts[i].pop_back();
	}

	// either of these work
	calc_reachable_dfs();
	// calc_reachable_floyd();

	for (int i = 1; i <= N; ++i)
		for (int g : gifts[i])
			if (reachable[g][i]) {
				cout << g << "\n";
				break;
			}
}

Danny Mittal's code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringJoiner;
import java.util.StringTokenizer;
 
public class RedistributingGifts {
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        int[][] rankings = new int[n + 1][n + 1];
        for (int cow = 1; cow <= n; cow++) {
            StringTokenizer tokenizer = new StringTokenizer(in.readLine());
            for (int rank = n; rank > 0; rank--) {
                rankings[cow][Integer.parseInt(tokenizer.nextToken())] = rank;
            }
        }
        boolean[][] reachable = new boolean[n + 1][n + 1];
        for (int cow1 = 1; cow1 <= n; cow1++) {
            for (int cow2 = 1; cow2 <= n; cow2++) {
                if (rankings[cow1][cow2] >= rankings[cow1][cow1]) {
                    reachable[cow2][cow1] = true;
                }
            }
        }
        for (int cow2 = 1; cow2 <= n; cow2++) {
            for (int cow1 = 1; cow1 <= n; cow1++) {
                for (int cow3 = 1; cow3 <= n; cow3++) {
                    reachable[cow1][cow3] = reachable[cow1][cow3] || (reachable[cow1][cow2] && reachable[cow2][cow3]);
                }
            }
        }
        StringJoiner joiner = new StringJoiner("\n");
        for (int cow = 1; cow <= n; cow++) {
            int bestGift = 0;
            for (int gift = 1; gift <= n; gift++) {
                if (rankings[cow][gift] > rankings[cow][bestGift] && reachable[cow][gift]) {
                    bestGift = gift;
                }
            }
            joiner.add(bestGift + "");
        }
        System.out.println(joiner);
    }
}

Additional Notes:

• This problem was inspired by the Top trading cycle algorithm.
• It is actually possible to solve this problem in $O(M)$ time, where $M$ is the number of edges in $G$, by computing the strongly connected components of $G$.
• Alternatively, this problem can be phrased as finding all edges that may be part of a perfect matching in a bipartite graph, given an initial perfect matching.