読者です 読者をやめる 読者になる 読者になる

GCJ 2016 Round 1A C: BFFs

GoogleCodeJam 競技プログラミング

解法

親友関係を有向グラフとして考える。頂点kの連結成分はk本の有向辺を持つため閉路を一つだけ含む。この閉路を構成する頂点数が2の時、これらは輪になって並べる時のパーツとして使うことができる。閉路を構成する頂点が3以上の時、この閉路を含む輪を作るにはこの閉路だけを使うしかない。

f:id:kenkoooo:20160423010627j:plain

f:id:kenkoooo:20160423010640j:plain

よって、求めるべき答えは、「作ることのできる一番大きい閉路」と「頂点数2の閉路を持つ連結成分の合計」の大きい方となる。

コード

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

template <class T, class U>
void chmax(T &t, U f) {
  if (t < f) t = f;
}

int invdfs(int v, int p, const vector<vector<int>> &inv) {
  int ma = 0;
  for (int next : inv[v]) {
    if (next == p) continue;
    chmax(ma, invdfs(next, p, inv));
  }
  return ma + 1;
}

int dfs(int v, int depth, const vector<int> &F, vector<int> &vis) {
  if (vis[v] >= 0) return depth - vis[v];
  vis[v] = depth;
  return dfs(F[v], depth + 1, F, vis);
}

int solve(const vector<int> &F) {
  int N = F.size();

  int uncircuit = 0;
  vector<vector<int>> inv(N);
  for (int i = 0; i < N; ++i) inv[F[i]].push_back(i);
  vector<bool> used(N, false);
  for (int i = 0; i < N; ++i) {
    if (used[i]) continue;
    int j = F[i];
    if (F[j] == i) {
      used[i] = true, used[j] = true;
      int from_i = invdfs(i, j, inv);
      int from_j = invdfs(j, i, inv);
      uncircuit += (from_i + from_j);
    }
  }

  int circuit = 0;
  for (int i = 0; i < N; ++i) {
    vector<int> vis(N, -1);
    if (vis[i] >= 0) continue;
    chmax(circuit, dfs(i, 0, F, vis));
  }

  return max(uncircuit, circuit);
}

int solve_naive(const vector<int> &F) {
  int N = F.size();
  vector<int> p(N);
  iota(p.begin(), p.end(), 0);
  int ma = 1;
  do {
    for (int n = ma; n <= N; ++n) {
      for (int i = 0; i < n; ++i) {
        int left = (i + n - 1) % n;
        int right = (i + 1) % n;
        int bff = F[p[i]];
        if (bff != p[left] && bff != p[right]) break;
        if (i == n - 1) chmax(ma, n);
      }
    }
  } while (next_permutation(p.begin(), p.end()));
  return ma;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int T;
  cin >> T;
  for (int testcase = 1; testcase <= T; ++testcase) {
    int N;
    cin >> N;
    vector<int> F(N);
    for (int i = 0; i < N; ++i) {
      cin >> F[i];
      F[i]--;
    }

    cout << "Case #" << testcase << ": ";
    cout << solve(F) << endl;
  }
}