この問題は、各人が持っているギフトを特定のルールに基づいて交換し、最終的に各人がどのギフトを受け取れるかを決定するものです。 各人は、自分自身と、自分より左側にいる人たちのギフトを受け取ることができます。具体的には、各行の初期ギフト配置において、そのギフトを右隣のギフトと結びつける一方向のエッジを考えます。

このグラフ構造において、各ノード（人）が属する強連通成分（SCC）が重要になります。あるノードが属する強連通成分内の他のノードが持つギフトは、交換を通じて最終的にそのノードが取得可能です。しかし、異なる強連通成分に属するノードのギフトは取得できません。

強連通成分を特定する方法として、以下の2つが考えられます。

1. Floyd-Warshall アルゴリズムによる伝達閉包の計算: グラフの全点対間の到達可能性を計算することで、強連通性を判断できます。この方法の時間計算量は O(N3) または bitset を用いた最適化で O(N3 / ω) となります。
2. Tarjan のアルゴリズムによる強連通成分分解: 深さ優先探索 (DFS) を利用して、グラフの強連通成分を直接特定します。この方法の時間計算量は O(N2) です。

最終的な出力として、各人が最終的に取得できるギフトのIDを出力します。もし、ある人が属する強連通成分内に、その人自身よりも右側にあるギフトが存在し、かつそのギフトから元の人のノードへの到達可能性があれば、そのギフトのIDを出力します。そうでなければ、その人自身の初期ギフトIDを出力します。

Floyd-Warshall (N=502) - 979ms

#include <iostream>
#include <vector>
#include <numeric>

const int MAXN = 502;
int n;
int adjacency[MAXN][MAXN];
bool reachability[MAXN][MAXN];
std::vector<int> outgoing_edges[MAXN];

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> n;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            std::cin >> adjacency[i][j];
        }
        for (int j = 1; j <= n; ++j) {
            if (adjacency[i][j] == i) break;
            reachability[i][adjacency[i][j]] = true;
            outgoing_edges[i].push_back(adjacency[i][j]);
        }
    }

    // Floyd-Warshall for transitive closure
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                reachability[i][j] = reachability[i][j] || (reachability[i][k] && reachability[k][j]);
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        bool found_gift = false;
        for (int neighbor : outgoing_edges[i]) {
            if (reachability[neighbor][i]) { // If an outgoing edge can reach back, it implies a cycle
                std::cout << neighbor << "\n";
                found_gift = true;
                break;
            }
        }
        if (!found_gift) {
            std::cout << i << "\n";
        }
    }

    return 0;
}

Floyd-Warshall with bitset (N=502) - 301ms

#include <iostream>
#include <vector>
#include <bitset>

const int MAXN = 502;
int n;
int adjacency_matrix[MAXN][MAXN];
std::bitset<MAXN> reachability_set[MAXN];
std::vector<int> forward_connections[MAXN];

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> n;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            std::cin >> adjacency_matrix[i][j];
        }
        for (int j = 1; j <= n; ++j) {
            if (adjacency_matrix[i][j] == i) break;
            reachability_set[i][adjacency_matrix[i][j]] = 1;
            forward_connections[i].push_back(adjacency_matrix[i][j]);
        }
    }

    // Floyd-Warshall using bitsets
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            if (reachability_set[i][k]) {
                reachability_set[i] |= reachability_set[k];
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        bool gift_assigned = false;
        for (int connected_node : forward_connections[i]) {
            if (reachability_set[connected_node][i]) { // Check if the connected node can reach back to i
                std::cout << connected_node << "\n";
                gift_assigned = true;
                break;
            }
        }
        if (!gift_assigned) {
            std::cout << i << "\n";
        }
    }

    return 0;
}

Tarjan's Algorithm (N=502) - 292ms

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

const int MAXN = 502;
int n;
int gift_assignment[MAXN][MAXN];
int discovery_time[MAXN];
int low_link_value[MAXN];
int scc_id[MAXN];
int timer;
int scc_count;
std::vector<int> adj_list[MAXN];
std::stack<int> node_stack;
std::vector<bool> on_stack;

void find_sccs(int u) {
    low_link_value[u] = discovery_time[u] = ++timer;
    node_stack.push(u);
    on_stack[u] = true;

    for (int v : adj_list[u]) {
        if (discovery_time[v] == 0) { // Not visited yet
            find_sccs(v);
            low_link_value[u] = std::min(low_link_value[u], low_link_value[v]);
        } else if (on_stack[v]) { // Visited and on current stack (back edge)
            low_link_value[u] = std::min(low_link_value[u], discovery_time[v]);
        }
    }

    if (low_link_value[u] == discovery_time[u]) { // Found an SCC root
        ++scc_count;
        while (true) {
            int node = node_stack.top();
            node_stack.pop();
            on_stack[node] = false;
            scc_id[node] = scc_count;
            if (node == u) break;
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> n;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            std::cin >> gift_assignment[i][j];
        }
        for (int j = 1; j <= n; ++j) {
            if (gift_assignment[i][j] == i) break;
            adj_list[i].push_back(gift_assignment[i][j]);
        }
    }

    on_stack.resize(n + 1, false);
    for (int i = 1; i <= n; ++i) {
        if (discovery_time[i] == 0) {
            find_sccs(i);
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            // If the gift assigned to person i belongs to the same SCC as person i
            if (scc_id[gift_assignment[i][j]] == scc_id[i]) {
                std::cout << gift_assignment[i][j] << "\n";
                break;
            }
        }
    }

    return 0;
}