Round Dance
题目出处
题目大意
给你 \(n\) 个顶点以及与每个顶点相连的一条边，将它们最终全部拼成一些简单环，问可以形成最少和最多的简单环的数量。输入保证合法。
知识点、思路
并查集
具体想法、推导
显然在最终的时刻，所有顶点一定只在一个环里。可以考虑用并查集维护每个顶点在哪个连通块中。最后用连通块的状态来解得答案。
由于输入合法（每个点的度保证小于等于 \(2\) ），所以每个含有 \(k\) 个顶点连通块最后的状态一定是形成了一个有 \(k\) 条边的环，或者是形成了一条含\(k-1\) 条边的链（如果少于 \(k-1\) 条边就不连通了）。
会产生链的原因，是因为输入时有可能含有重复的边。
例如
6
2 1 4 3 6 5
\(1,2 ; 3,4 ; 5,6\) 分别形成了三条链，能形成环最多的情况是每条链都自身头尾相连，这样能形成三个环，能形成环最少的情况是，所有的链头尾相连形成一个大环。
为了记录重复边，可以使用 \(std::map\) , 记录并查集的顶点数和不重复的边数，可以通过在并查集的合并过程中同时维护两个数组。
示例代码
int p[N], sz[N], cnt[N];
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
void merge(int a,int b){
if (find(a)==find(b)) return;
sz[find(b)]+=sz[find(a)];
cnt[find(b)]+=cnt[find(a)];
p[find(a)]=find(b);
}
void solve()
{
cin>>n;
for (int i=1;i<=n;i++) cin>>a[i];
int cnt1=0,cnt2=0;
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
sz[i]=1;
cnt[i]=0;
}
map<pii,int> mp;
for (int i=1;i<=n;i++) {
int aa=a[i],bb=i;
if (aa>bb) swap(aa,bb);
merge(aa,bb);
if (!mp.count({aa,bb})){
cnt[find(bb)]++;
mp[{aa,bb}]++;
}
}
bool re=false;
for (int i=1;i<=n;i++){
if (p[i]!=i) continue;
if (sz[i]==cnt[i]) cnt1++;
else re=true;
cnt2++;
}
if (re) cnt1++;
cout<<cnt1<<' '<<cnt2<<endl;
}