Problem - E - Codeforces
题意：
思路：
显然，最大值就是什么边都不连的连通块个数，最小值就是能连的都连上
那就是，如果一个连通块存在度为1的点，就把它当作接口连接文章来源：https://www.toymoban.com/news/detail-603365.html
Code：文章来源地址https://www.toymoban.com/news/detail-603365.html
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mxn=2e5+10;
int N,x;
int F[mxn],FG[mxn],sz[mxn];
set<int> G[mxn];
int find(int x){
return F[x]=(x==F[x])?x:find(F[x]);
}
void join(int u,int v){
int f1=find(u),f2=find(v);
if(f1!=f2){
F[f1]=f2;
sz[f2]+=sz[f1];
}
}
void solve(){
cin>>N;
for(int i=1;i<=N;i++){
F[i]=i;
sz[i]=1;
G[i].clear();
FG[i]=0;
}
for(int i=1;i<=N;i++){
cin>>x;
G[i].insert(x);
G[x].insert(i);
join(x,i);
}
for(int i=1;i<=N;i++){
FG[find(i)]|=(G[i].size()==1);
}
int cnt=0,res=0;
for(int i=1;i<=N;i++){
if(find(i)==i){
res++;
cnt+=FG[i];
}
}
cout<<min(res,res-cnt+1)<<" "<<res<<'\n';
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int __=1;cin>>__;
while(__--)solve();return 0;
} 到了这里，关于【简单图论】CF1833 E的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
