Analysis: Reorder by Brian Dean

To solve this problem, we simply loop over all cycles, counting them and remembering the longest cycle during the process. We keep track of which elements we have visited, so that we only visit each element once. My code is below:

#include <iostream>
#include <fstream>
#define MAX_N 100
using namespace std;

int A[MAX_N+1], B[MAX_N+1];
int done[MAX_N+1], where_in_B[MAX_N+1], N;

int trace_cycle(int start)
{
  int count = 0;
  int i = start;
  do {
    done[i] = 1;
    i = where_in_B[A[i]];
    count++;
  } while (i != start);
  return count;
}

int main(void)
{
  int num_cycles = 0, longest_cycle = -1;
  ifstream fin ("reorder.in");
  fin >> N;
  for (int i=1; i<=N; i++) fin >> A[i];
  for (int i=1; i<=N; i++) {
    fin >> B[i];
    where_in_B[B[i]] = i;
  }
  fin.close();
  for (int i=1; i<=N; i++) 
    if (A[i] != B[i] && !done[i]) {
      int len = trace_cycle(i);
      if (len > longest_cycle) longest_cycle = len;
      num_cycles++;
    }
  ofstream fout ("reorder.out");
  fout << num_cycles << " " << longest_cycle << "\n";
  fout.close();
  return 0;
}