GCJ 2016 Round 1A C: BFFs
解法
親友関係を有向グラフとして考える。頂点kの連結成分はk本の有向辺を持つため閉路を一つだけ含む。この閉路を構成する頂点数が2の時、これらは輪になって並べる時のパーツとして使うことができる。閉路を構成する頂点が3以上の時、この閉路を含む輪を作るにはこの閉路だけを使うしかない。
よって、求めるべき答えは、「作ることのできる一番大きい閉路」と「頂点数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; } }