CFR 742 C. Arpa's loud Owf and Mehrdad's evil plan ( Ad hoc )

Problem - C - Codeforces

題意：
給一個圖，每個節點都有一個連向另一個點的有向邊。求最小的 t，且 t ≥ 1，使得從每個節點 x 出發沿著有向邊走 t 次後達到的 y，從 y 出發沿著有向邊走 t 次也達到 x。若無法達成輸出 -1。

資料規模：
節點數 1 ≤ N ≤ 100

解法：
若且唯若有一個點不在某個環裡，會無解，因為從它出發達到的任一個節點一定不可能達到他。
對於一個奇環，必須要是環長度的倍數才可以滿足條件。
對於偶還，必須要是環長度的一半的倍數才可以滿足條件。
因此求其最小公倍數便是答案。

時間 / 空間複雜度：
O( N )

int N;
vi C;

void init(){
  cin >> N;
  C = vi( N );
  for( int i = 0; i < N; ++i )
    cin >> C[ i ], --C[ i ];
}

vi cyc;

void preprocess(){
  for( int i = 0; i < N; ++i ){
    int len = 1;
    for( int u = C[ i ]; u != i; u = C[ u ] ){
      if( ( u == C[ u ] and u != i ) or len > 100 )
        cout << -1 << endl, exit( 0 );
      ++len;
    }
    if( len % 2 == 1 )
      cyc.push_back( len );
    else
      cyc.push_back( len / 2 );
  }
}

void solve(){
  ll ans = 1LL;
  for( int i = 0; i < cyc.size(); ++i )
    ans = ans * cyc[ i ] / __gcd( ans, 1LL * cyc[ i ] );
  cout << ans << endl;
}