并查集 n个传送阵可能会构成多个环，利用并查集把n个传送阵构造成若干个环，并让每个根节点记录对应环的长度。 最后遍历每个传送阵，判断当前传送阵和前后邻近的传送阵是否连通，不连通则说明可以使用魔法，将两个环的长度加起来；连通则说明在同一个环里。结果取最大值 ``` #include <iostream> using namespace std; const int N = 1e6+2; int n; int fa[N]; void init() { for(int i = 1;i<=n;i++) fa[i] = i; } int root(int x) { return fa[x] = (x == fa[x]? x : root(fa[x])); } void add(int x ,int y) { if(root(x) != root(y)) { fa[root(x)] = root(y); } } int main() { cin>>n; int next[n+1]; int num[n+2] = {0}; bool v[n+1] = {0}; init(); for(int i = 1;i<=n;i++) { cin>>next[i]; } for(int i = 1;i<=n;i++) { if(v[i]) continue; v[i] = true; int now = i; int cnt = 1; while(next[now] != i) { add(now, next[now]); v[next[now]] = true; now = next[now]; cnt++; } num[root(i)] = cnt; } int ans = 0; for(int i = 1;i<=n;i++) { if(root(i)!= root(i-1)) ans = max(ans, num[root(i)] + num[root(i-1)]); if(root(i) != root(i+1)) ans = max(ans, num[root(i)] + num[root(i+1)]); } cout<<ans; return 0; } ```

并查集 话说这个不应该是签到题吗? 怎么上强度了qwq ```cpp #include <iostream> #include <string> #include <vector> #include <numeric> using namespace std; using ll = long long; struct USet { vector<int> fa; vector<int> cnt; int cc; USet(int size) : fa(vector<int>(size)) , cnt(vector<int>(size, 1)) , cc(size) { iota(fa.begin(), fa.end(), 0); } int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } void maga(int from, int to) { int x = find(from); int y = find(to); if (x == y) return; fa[x] = y; cnt[y] += cnt[x]; } bool isSame(int x, int y) { return find(x) == find(y); } int getCnt(int x) { return cnt[find(x)]; } }; int main() { int n; cin >> n; USet uset(n); for (int i = 0; i < n; ++i) { int x; cin >> x; uset.maga(x - 1, i); } int res = 0; for (int i = 0; i < n; ++i) { res = max(res, uset.getCnt(i)); if (i > 0) { if (!uset.isSame(i - 1, i)) res = max(res, uset.getCnt(i - 1) + uset.getCnt(i)); } else if (i < n - 1) { if (!uset.isSame(i + 1, i)) res = max(res, uset.getCnt(i + 1) + uset.getCnt(i)); } } cout << res << '\n'; return 0; } ```

``` #include <bits/stdc++.h> #define int long long using namespace std; const int N=1e6+10; int a[N],p[N],cnt[N],sum,n; int find(int x){ if(p[x]!=x) p[x]=find(p[x]); return p[x]; } signed main() { cin>>n; for(int i=1;i<=n;i++){ p[i]=i; cnt[i]=1; } for(int i=1;i<=n;i++){ int x; cin>>x; int a=find(i),b=find(x); if(a==b) continue; p[b]=a; cnt[a]+=cnt[b]; } for(int i=1;i<=n;i++){ int a=find(i),b=find(i+1); if(a==b) sum=max(sum,cnt[a]); else{ sum=max(sum,cnt[a]+cnt[b]); } } cout<<sum<<endl; return 0; } ```

``` #include<iostream> #include<vector> using namespace std; int flag = true; int all = false; int flag1 = false; int ans = 0; void dfs(vector<int>& a, vector<int>& vis, int pos, int pre, int Temp)//pos代表在第几个传送阵 { if (ans < Temp)ans = Temp; if (Temp == a.size() - 1)return;//深度为传送阵数量，则返回 if (!vis[pos]) { vis[pos] = true; dfs(a, vis, a[pos], pos, Temp + 1);//pos未走过，将vis设置为走过 } //走到此则说明开始循环 //试探破局之法 if (!flag)return;//没有魔法，破不了； if (pos == 1 && !vis[2]) flag = false, dfs(a, vis, 2, pre, Temp), vis[2] = false, flag = true;//第二个点没走过，则走一下 if (pos > 1 && pos < a.size() && !vis[pos - 1]) flag = false, dfs(a, vis, pos - 1, pre, Temp), vis[pos - 1] = false, flag = true; if (pos > 1 && pos < a.size() - 1 && !vis[pos + 1])flag = false, dfs(a, vis, pos + 1, pre, Temp), vis[pos + 1] = false, flag = true; if (pos == pre)//走到试探末端了，回去 { flag1 = true; return; } if (flag1)return; dfs(a, vis, a[pos], pre, Temp);//继续试探下一个 } int main() { int n; cin >> n; vector<int> a(n + 1);//传送阵，从第一个开始，0无 vector<int> vis;//是否走过该传送阵 vis.resize(n + 1, 0); int Temp = 0; for (int i = 1; i <= n; i++)cin >> a[i];//输入传送阵能传送到第几传送阵 for (int i = 1; i <= n; i++)//试探每一个初始点 { dfs(a, vis, i, 0, Temp); } cout << ans; return 0; } ```

``` #include <bits/stdc++.h> #define int long long using namespace std; typedef pair<int,int> pii; const int N=1000000+10; int n,ans; int a[N],fa[N],cnt[N]; void init() { for(int i=1;i<=n;i++) { fa[i]=i; cnt[i]=1; } } int find(int x) { if(fa[x]==x) return x; else return fa[x]=find(fa[x]); } void union_(int x,int y) { x=find(x); y=find(y); if(x!=y) { fa[x]=y; cnt[y]+=cnt[x]; } } void solve() { cin>>n; init(); for(int i=1;i<=n;i++) { cin>>a[i]; union_(i,a[i]); } for(int i=1;i<=n;i++) { ans=max(ans,cnt[find(i)]); if(find(i)!=find(i+1)) { ans=max(ans,cnt[find(i)]+cnt[find(i+1)]); } } cout<<ans; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; t=1; // cin>>t; while(t--) { solve(); } return 0; } ```

``` #include<bits/stdc++.h> using namespace std; const int N = 1e6 + 10; int n; int a[N]; int belong[N];//第i个点属于第几个环 int cnt[N];//维护每一个环的个数 int idx;//到第几个环 void solve(){ cin >> n; for(int i = 1; i <= n; i ++){ cin >> a[i]; } idx = 1; for(int i = 1; i <= n; i ++){ if(!belong[i]){ belong[i] = idx; cnt[idx] ++; int temp = i; while(a[temp] != i){ temp = a[temp]; belong[temp] = idx; cnt[idx] ++; } idx ++; } } if(idx == 2){ cout << n; return ; } int ans = 0; for(int i = 2; i <= n; i ++){ if(belong[i] != belong[i - 1]){ ans = max(ans, cnt[belong[i]] + cnt[belong[i - 1]]); } } cout << ans; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); return 0; } ```