Functional Graph構造体を作った。なもりグラフ

ライブラリ

説明

  • 問題 https://atcoder.jp/contests/abc357/tasks/abc357_e
  • Functional Graphの問題だと見抜けた後は、連結成分ごとに分けて考えて、それぞれ閉路部分がどこか求めるなど、よく求める形がありそうなので再利用を考えて構造体にした
  • FunctionalGraph構造体
    • 複数（もしくは1つ）の、連結成分ごとに分離された、なもりグラフを持つ
  • Namori構造体
    • なもりグラフ
    • 各頂点は連結
    • 下記画像のような形で、閉路とそれに刺さってくる頂点の形

使用例

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N;cin>>N;

    // iからA[i]への辺
    VI A(N);
    rep(i, N){
      cin >> A[i]; A[i]--;
    }

    ll ans=0;
    auto fg = FunctionalGraph(A);
    // 連結されたなもりグラフそれぞれについて
    for(auto namori : fg.namoris){
      for(ll id : namori.ids){
        // サイクルも深さも取れるよ
        ans += namori.cycle_ids.size() + namori.depth[id];
      }
    }
    p(ans);

    return 0;
}

verified

用語（閉路、ループ）

GPT

Cycle: 
　グラフ理論において、特に意味が明確で、同じ頂点を
　2度通らずに出発点に戻ってくる経路を指します。
Loop: 
　通常、自己ループを指し、1つの頂点から同じ頂点に戻るエッジを意味します。

したがって、一般的な「閉路」を指す場合は「cycle」が適切です。