Redistributing Gifts (USACO Silver 2022 February)

要计算的是牛 $i$ 最希望收到的礼物，所以有可能一个礼物会被多头牛选择，如果它们都喜欢这个礼物，结果可能会有重复。

算法：验证每一个 $i$ 更喜欢的礼物是否有可行性：从 $i$ 出发DFS，在 $x$ 结点，遍历所有有 $x$ 需要的礼物的牛，如果走出一个环，则是可行的。

批量找环的技巧：注意对每个节点做DFS来找环会TLE，我们可以把可到达的结果缓存起来，这样对于牛 $i$ ，喜欢的礼物 $g$ ，如果倒过来，reachable[g][i]为真，则就找到一个环。这来就大幅减少计算量。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n;
int p[505][505];
bool vis[505];
 
int ans[505];
int orig;
bool cycle = false;
 
bool reachable[505][505];
 
// dfs to fill in reachable[][]
void dfs(int src, int x) {
    if (reachable[src][x])
        return;
    reachable[src][x] = true;
    for (int g : p[x]) {
        if (g == x)
            break;
        dfs(src, g);
    }
}
 
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            scanf("%d", &p[i][j]);
 
    // pre-calculate reachability matrix
    for (int i = 1; i <= n; i++)
        dfs(i, i);
 
    for (int i = 1; i <= n; i++) {
        for (int g: p[i]) {
            if (reachable[g][i] || g == i) {
                printf("%d\n", g);
                break;
            }
        }
    }
 
    return 0;
}