CF1833E 题解
Geoyster
·
·
题解
CF1833E Round Dance
比赛做出来了，但是看别人都是直接跑图，这里提供一种并查集做法。
题目大意
## 思路
显然知道相邻关系可以当作图来看待，但是我们只要知道最终的可能组数，不妨考虑并查集。
先当作最多组数考虑。只要将所有相邻关系合并，最后数组数就行了。
再考虑最少组数。即将能和并的尽量合并。那么如何确定一个组能否去合并呢？以下分两种情况
1. 组内人数 $\geq 3$ 当边数等于点数时形成环，在题目背景下即相邻关系数等于组内人数。不能再合并。不形成环则可以。
2. 组内人数 $=2$ 无论如何都可以与其他组合并，应为确定相邻关系至多一条。
然后将能和并的看成一组即为最小组数。
## 实现
[并查集](https://oi-wiki.org/ds/dsu/)，其实基本都是套模板，判断构成环只要看要连接的两点是否已在一个根节点下，是则有环，反之无环。然后重边也要特判一下。关于不可合并组，我是在找到环后就记录，如果这个值比总组数小则必然又可以构成一个可合并的组。
## AC CODE
```
#include<bits/stdc++.h>
using namespace std;
int t,n;
struct dsu{
int fa[200005],n;
void ini(){
for(int i=1;i<=n;i++) fa[i]=i;
}
int find(int a){
return fa[a]==a?a:fa[a]=find(fa[a]);
}
int cnt(){
int res=0;
for(int i=1;i<=n;i++) if(fa[i]==i) res++;
return res;
}
};
void solve(){
cin>>n;
dsu d; d.n=n; d.ini();
int mn=0,mx=n;
map<pair<int,int>,bool> exist;
for(int i=1;i<=n;i++){
int u; cin>>u;
if(exist[make_pair(u,i)]) continue;
exist[make_pair(i,u)]=1;
int t1=d.find(u),t2=d.find(i);
if(t1==t2) mn++;
else d.fa[t1]=t2;
}
mx=d.cnt();
if(mx>mn) mn++;
printf("%d %d\n",mn,mx);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>t;
while(t--) solve();
return 0;
}
```