Codeforces Round #383 (Div. 2) C. Arpa’s loud Owf and Mehrdad’s evil plan dfs+最小公倍数

My Solution

题意：当一个人开始是另一个人结束，但这个人开始时前面那个人结束，具体还是请看题吧，哈哈

dfs+最小公倍数

每个人只能且必须处于一个环中，自环也是环，如果环的元素个数是奇数则这个环必须是ansi =  k*cnt，如果是偶数则 ans = k * (cnt / 2);//这个是自己画图发现的规律。

这题不用多想什么优化的方法，搞复杂了反而容易错(比如笔者自己 T _ T )，n <= 100，直接对于每一个点每层dfs时cnt++，

直到找到 目标 find(u, v)，，或者找到根节点时，或者 cnt > 100 时return。//这个100是自己设定的，即最多100个节点cnt大于100说明ans = -1。

比如

5
2 4 3 1 2

这组数据。

找出每个环的ansi，然后对这些ansi取最大公约数即可，a、b最大公约数等于 a * b / (gcd(a, b))，且注意中间过程溢出，因为这里有 a * b了

复杂度 O(n^2)

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 1e2 + 8;

int cnt;
bool flag[maxn];
queue que;

int father[maxn], _rank[maxn];
inline void DisjointSet(int n)
{
    for(int i = 0; i <= n; i++){
        father[i] = i;
    }
}

inline bool _find(int v, int u)
{
    if(father[v] == u){
        //cout << cnt << endl; if(cnt % 2 == 1){ que.push(cnt); } else{ que.push(cnt / 2); } return true; } else if(father[v] == v){ return false; } else{ cnt++; if(cnt == 1024) return false; if(!_find(father[v], u)){ return false; } else return true; } } inline LL gcd(LL a, LL b) { return b == 0 ? a : gcd(b, a % b); } int main() { #ifdef LOCAL freopen("c.txt", "r", stdin); //freopen("c.out", "w", stdout); int T = 4; while(T--){ #endif // LOCAL ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n;
    DisjointSet(n);
    for(int i = 1; i <= n; i++){ cin >> father[i];
    }

    LL ans = 1;
    for(int i = 1; i <= n; i++){
        cnt = 1;
        if(!_find(i, i)){
            ans = 1024;
            break;
        }
    }
    if(ans != 1024){
        ans = que.front();
        que.pop();
        while(!que.empty()){
            ans = (ans * que.front()) / gcd(ans, que.front());
            //!WA 61 这里溢出了，换成LL 以后过了， 毕竟求的是最小公倍数
            que.pop();
        }
        cout << ans << endl;
    }
    else cout << -1 << endl;



    #ifdef LOCAL
    memset(flag, false, sizeof flag);
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx