题解归档 - cf755C

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf755C
• 本地来源：problems/cf755C/idea.md
• 题目链接：https://codeforces.com/contest/755/problem/C
• 原始标题：755C PolandBall and Forest

思路

755C PolandBall and Forest

题意

森林里有 (n) 个点，每点一人，编号 (1..n)。已知 (p_i)：与 (i) 在同一棵树里、距离 (i) 最远的点的编号（若有多个取最小编号）。保证 (p) 来自某合法森林。求树的数量。

思路

若 (i) 与 (p_i) 在同一棵树且 (p_i \ne i)，则 (i) 与 (p_i) 之间必有边（否则 (p_i) 不可能是同一棵树上的最远点）。

对所有 (p_i \ne i) 做并查集合并 ((i, p_i))，初始 (ans=n)，每次成功合并 (ans--)。最终 (ans) 即连通块数 = 树的数量。

证明直觉：序列 (p) 由真实森林唯一确定每条「最远点对」边；合并后不会跨树连边；同一棵树内所有点通过这类边连通。

模板

并查集基础（路径压缩），未使用 lib/ 中带权并查集。

ll find(ll x){
    if(f[x]!=x) f[x]=find(f[x]);
    return f[x];
}
void merge(ll x,ll y){
    x=find(x), y=find(y);
    if(x!=y) f[x]=y, ans--;
}

复杂度

• 时间：(O(n\,\alpha(n)))
• 空间：(O(n))

验证

• 样例：✅
• 对拍：200 组随机森林生成 (p) → stress.py 通过

结果

• CF 提交 #377693084 — AC
• 模板已沉淀：lib/数据结构(并查集).cpp

代码

来源：problems/cf755C/solution.cpp

/* Author: likely
 * Time: 2026-06-08 04:10:00
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=10005;
ll f[maxn+5],n,i,p[maxn+5],ans;
ll find(ll x){
    if(f[x]!=x) f[x]=find(f[x]);
    return f[x];
}
void merge(ll x,ll y){
    x=find(x),y=find(y);
    if(x!=y) f[x]=y,ans--;
}
int main(){
    cin>>n;
    for(i=1;i<=n;i++) f[i]=i;
    ans=n;
    for(i=1;i<=n;i++){
        cin>>p[i];
        if(p[i]!=i) merge(i,p[i]);
    }
    cout<<ans<<"\n";
    return 0;
}