解题思路:因为a 是 1 至 n 的一个排列,所以每个点的入度与出度都是1,我们将可以互通的点并成一个集合,最后在使用魔法就好
注意事项:
参考代码:
#include<bits/stdc++.h> using namespace std; int a[1000005]; int f[1000005]; bool vis[1000005]; int siz[1000005]; int find(int x) { if(f[x]!=x) { return f[x]=find(f[x]); } return x; } void meare(int x,int y) { int a,b; a=find(x); b=find(y); if(a!=b) { if(siz[a]>siz[b]) { swap(a,b); } f[a]=b; siz[b]+=siz[a]; } } void dfs(int i) { vis[i]=1; meare(i,a[i]); if(!vis[a[i]]) { dfs(a[i]); } } int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } for(int i=1;i<=n;i++) { f[i]=i; siz[i]=1; } for(int i=1;i<=n;i++) { if(!vis[i]) { dfs(i); } //cout<<siz[find(i)]<<' '; } int ans=siz[find(1)]; for(int i=1;i<n;i++) { if(find(i)!=find(i+1)) { ans=max(ans,siz[find(i)]+siz[find(i+1)]); } } printf("%d",ans); return 0; }
0.0分
5 人评分
C语言程序设计教程(第三版)课后习题4.9 (C++代码)浏览:2149 |
2005年春浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:720 |
printf基础练习2 (C语言代码)浏览:593 |
C语言训练-排序问题<1> (C++代码)浏览:598 |
简单的a+b (C++语言代码)浏览:858 |
C语言程序设计教程(第三版)课后习题10.4 (C语言代码)浏览:675 |
C语言程序设计教程(第三版)课后习题7.3 (C语言代码)浏览:1195 |
C语言程序设计教程(第三版)课后习题6.5 (C++代码)浏览:456 |
简单的a+b (C语言代码)浏览:605 |
【计算两点间的距离】 (C语言代码)浏览:1493 |