CF1327D. Infinite Path

发表于 | 阅读数

定义$c=a\times b\rightarrow c[i]=a[b[i]]$,定义每$i$点都有颜色$c_i$,求最小的$k$使得$p^k$这个序列存在$p[i],p[p[i]]..$为相同颜色。

考虑$p^k[i]=p[p[p[..]]]$,若在建立$i\rightarrow p[i]$也就是第$i的第k$个结点。如果要产生颜色一样,一定是形成结点颜色相投的环。

并且可以知道这个环是在原本环上新建的。对于一个环枚举他包含的环，环之间间隔需要$k|size$,不然每个点还是都要访问一边。即枚举一个环的因子。遍历对应环上所有的点。时间复杂度$O(n\sqrt n )$

代码 ```c++ #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const int N = 2e5 + 10; const int mod = 1e9 + 7; vector s, g[N]; int n, c[N], p[N], v[N]; int main() { for (int i = 1; i < N; i++) for (int j = i; j < N; j += i) g[j].push_back(i); int T; scanf("%d", &T); while (T--) { scanf("%d", &n); int ans = 1e9; for (int i = 1; i <= n; i++) v[i] = 0; for (int i = 1; i <= n; i++) scanf("%d", p + i); for (int i = 1; i <= n; i++) scanf("%d", c + i); for (int i = 1; i <= n; i++) if (!v[i]) { s.clear(); int to = i; while (v[to] == 0) { s.push_back(c[to]); v[to] = 1; to = p[to]; } int siz = s.size(); if (siz == 1) { ans = 1; break; } for (int x : g[siz]) { for (int t = 0; t < x; t++) { bool flag = 1; for (int j = t; j < siz; j += x) if (s[t] != s[j]) flag = 0; if (flag) ans = min(x, ans); } } } printf("%d\n", ans); } }