并查集WA了九个点
查看原帖
并查集WA了九个点
169756
zcayyds楼主2021/9/7 22:31

代码如下,```cpp #include<bits/stdc++.h> using namespace std; const int xxh=200003; int n,fa[xxh],tem,ans=INT_MAX,size[xxh]; int find(int x){ if(x==fa[x])return x; return fa[x]=find(fa[x]); } void join(int c1,int c2){ int f1=find(c1),f2=find(c2); if(f1!=f2){ fa[f2]=f1; size[f1]+=size[f2]; size[f2]+=size[f1];//把f2的大小也加上去,不加会错 } } inline int read(){ int sum=0,f=1; char c=getchar(); while(c<'0'||c>'9'){ if(c=='-')f=-1; c=getchar(); } while(c>='0'&&c<='9'){ sum=sum10+c-'0'; c=getchar(); } return sumf; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); n=read(); for(int i=1;i<=n;i++){fa[i]=i;size[i]=1;} for(int i=1;i<=n;i++){tem=read();join(i,tem);} for(int i=1;i<=n;i++)ans=min(ans,size[i]); cout<<ans; return 0; }

2021/9/7 22:31
加载中...