USACO 2017 December Contest Silver Division - The Bovine Shuffle

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

The answer is just the length of each "cycle" part of a connected graph, as eventually all the chains leading into the cycle will be reduced and only the cycle part will remain.

Source code

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

Solution 1

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    ifstream cin("shuffle.in");
    ofstream cout("shuffle.out");
    int n;
    cin >> n;

    vector<int> next(n);
    vector<int> degrees(n);
    for (int i = 0; i < n; i++) {
        cin >> next[i];
        next[i]--;
        degrees[next[i]]++;
    }

    queue<int> q;
    int counter = 0;
    for (int i = 0; i < n; i++) {
        if (degrees[i] == 0) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int current = q.front();
        counter++;
        q.pop();
        degrees[next[current]]--;
        if (degrees[next[current]] == 0) {
            q.push(next[current]);
        }
    }
    cout << n - counter << '\n';
    return 0;
}

Solution 2

#include <fstream>
#include <iostream>
using namespace std;

int answer[100001];
int arr[100001];

int dfs(int i) {
    int a = arr[i];
    int b = arr[arr[i]];
    while (a != b && answer[a] == 0 && answer[b] == 0) {
        a = arr[a];
        b = arr[arr[b]];
    }
    if (answer[a] != 0) {
        int c = a;
        a = i;
        while (a != c) {
            answer[a] = answer[c];
            a = arr[a];
        }
        return 0;
    }
    if (answer[b] != 0) {
        int c = b;
        b = i;
        while (b != c) {
            answer[b] = answer[c];
            b = arr[b];
        }
        return 0;
    }
    int length = 1;
    a = arr[a];
    while (a != b) {
        length++;
        a = arr[a];
    }
    a = i;
    while (answer[a] == 0) {
        answer[a] = length;
        a = arr[a];
    }
    return length;
}

int main() {
    ifstream cin("shuffle.in");
    ofstream cout("shuffle.out");

    int n;
    cin >> n;
    long long sol = 0;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    for (int i = 1; i <= n; i++) {
        if (!answer[i]) {
            sol += dfs(i);
        }
    }
    cout << sol << '\n';
    return 0;
}