Codeforces Round #383 (Div. 2) C. Arpa's loud Owf and Mehrdad's evil plan（dfs+数学思想）

题目链接：http://codeforces.com/contest/742/problem/C

题意：题目比较难理解，起码我是理解了好久，就是给你n个位置每个位置标着一个数表示这个位置下一步能到哪个位置，然后要求

求一个数t，保证经过t步x能到达y，而且y经过t步能到x，而且是所有点都要满足。

这题只有一种情况是无法得到结果的，那就是有两个以上的点通向同一个位置。其实题目中也略微有点提示。

然后剩下的就差不多靠暴力解决，但还是有点技巧的。

注意要满足题目中要求其实就是找单向联通块，如果联通数为偶数那么就可以折半，否则就为循环到自己。

然后求各个联通块的gcd即可。

#include <iostream>

#include <cstring>

#include <algorithm>

#include <cstdio>

using namespace std;

const int M = 110;

int gcd(int a , int b) {

    return b ? gcd(b , a % b) : a;

}

int vis[M] , Next[M] , have[M];

int dfs(int pos) {

    if(vis[Next[pos]])

        return 0;

    vis[Next[pos]] = 1;

    return 1 + dfs(Next[pos]);

}

int main() {

    int n;

    scanf("%d" , &n);

    int flag = 0;

    for(int i = 1 ; i <= n ; i++) {

        scanf("%d" , &Next[i]);

        have[Next[i]]++;

        if(have[Next[i]] > 1)

            flag = 1;

    }

    if(flag == 1) {

        printf("-1\n");

    }

    else {

        int ans = 1;

        for(int i = 1 ; i <= n ; i++)

            vis[i] = 0;

        for(int i = 1 ; i <= n ; i++) {

            if(vis[i])

                continue;

            int l = dfs(i);

            if(l % 2 == 0)

                l /= 2;

            ans = (ans * l) / gcd(ans , l);

        }

        printf("%d\n" , ans);

    }

    return 0;

}

巴特西

Codeforces Round #383 (Div. 2) C. Arpa's loud Owf and Mehrdad's evil plan（dfs+数学思想）

最新文章

热门文章