USACO 2021 January Contest Silver Division - Dance Mooves#

Problem link: here

Problem Solution#

We can simulate the \(k\) moves. While simulating these moves, we remember for each cow which positions it visits. At the end of the \(k\) moves we notice that there are cows in other positions than the initial one. We can look at this positioning as if it were a graph: at the end there will be a number of connected components, and the nodes in these connected components have the same distinct positions that they go to (because, if we make \(n\) sets of moves, the graph will end up being a cycle). Thus, knowing for each cow which positions it visits after \(k\) moves, for each node in a connected component there will be the same answer: the number of distinct positions that any cow in the connected component goes to.

Source code#

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

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

const int MOD = 1e9 + 7;

int N, K;
int goTo[100001];
set<int> passed[100001];
int ans[100001];
bool seen[100001];
set<int> setUnion;

void DFS(int u) {
    if (seen[u]) 
        return;
    seen[u] = true;
    for (auto v : passed[u]) 
        setUnion.insert(v);
    DFS(goTo[u]);
    ans[u] = (int)setUnion.size();
}

int main() {
    cin >> N >> K;
    for (int i = 1; i <= N; i++) {
        goTo[i] = i;
        passed[i].insert(i);
    }
    while (K--) {
        int a, b;
        cin >> a >> b;
        swap(goTo[a], goTo[b]);
        passed[goTo[a]].insert(a);
        passed[goTo[b]].insert(b);
    }
    for (int i = 1; i <= N; i++) {
        if (!seen[i]) {
            setUnion.clear();
            DFS(i);
        }
        cout << ans[i] << "\n";
    }
    return 0;
}