D: mod rally ～ACL sccを用いて強連結成分分解～

• Quiz
  • https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2020Day3/problems/D
• AC
  • https://onlinejudge.u-aizu.ac.jp/beta/review.html#ACPC2020Day3/4862555
• 解説
  • 強連結成分分解する
  • 始点の強連結グループからトポロジカル順にDPして最大距離を求める
  • 最大距離のうちの最大値＝強連結成分をつなぐ辺数ならYes
• ACL
  • atcoder-library sccを使用
  • https://atcoder.github.io/ac-library/document_ja/scc.html

#include <atcoder/scc>
using namespace atcoder; // 忘れがち

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

    // input
    ll N,M;
    cin>>N>>M;

    VI A(N);
    rep(i, N) cin >> A[i];

    auto g = scc_graph(M);
    FOR(i,1,M){
      for(ll a : A){
        ll to = (i*a)%M;
        if(i==to)continue;
        g.add_edge(i,to);
      }
    }

    // 強連結成分分解
    auto G = g.scc();
    ll sz = SZ(G);

    // 各頂点がどのグループに属するかのテーブル
    VI Group(M);
    rep(i,sz){
      for(ll a : G[i]) Group[a] = i;
    }

    VI dist(sz, 0);

    // トポロジカル順にDPして始点からの距離を求める
    ll ma = 0;
    rep(i,sz){
      for(ll from : G[i]){
        for(ll a : A){
          ll to = (from*a)%M;
          if(Group[from]==Group[to])continue;
          chmax(dist[Group[to]], dist[Group[from]]+1);
          chmax(ma, dist[Group[to]]);
        }
      }
    }

    if(ma==sz-1) yes();
    no();

    return 0;
}