USACO 2022 February Contest Silver Division - Redistributing Gifts

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We want to think at some sort of a graph which helps us model the relations between the cows. Naturally, in order for two cows to be able to improve their gifts, there has to be some cycle which links them in a positive manner (like \(2\) and \(3\) in the sample test case).

A starting idea is to think at the links between \(i\) and \(j\) such that in \(i\)'s distribution, \(j\) is preferred to \(i\). Now, in order to see if we have a cycle between two vertexes \(i\) and \(j\), two conditions must be fulfilled:

• \(i\) can reach \(j\)
• \(j\) can reach \(i\)

In order to find these conditions, we can just do a DFS from each vertex and find the vertexes it can reach.

Source code

The source code in C++ can be seen below.

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

vector<vector<int> > graph;

int cnt;

void dfs (int node, int start, vector<vector<int> > &reach) {
    reach[start][node] = 1;
    for (auto x : graph[node]) {
        if (!reach[start][x]) {
            dfs(x, start, reach);
        }
    }
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<vector<int> > order(n+1, vector<int> (n+1));
    vector<vector<int> > reach(n+1, vector<int> (n+1));

    graph.resize(n+1);

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> order[i][j];
        }

        for (int j = 1; j <= n; j++) {
            graph[i].push_back(order[i][j]);
            if (order[i][j] == i) {
                break;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        dfs(i, i, reach);
    }

    for (int i = 1; i <= n; i++) {
        for (auto x : graph[i]) {
            if (reach[x][i]) {
                cout << x << '\n';
                break;
            }
        }
    }

    return 0;
}