14235: 【原4235】不等的数

题目

题目描述

author: fur 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4235

相等的数

题目描述

现在有\(n\)个数，其构成序列\({a_i}\)（0-base），它们之间也有大小关系，对于每个数我们都能知道一个大于等于它的数，对于第\(i\)个数我们知道第\(g_i\)个数是大于等于它的，即\(a_i\leq a_{g_i}\)
碰巧的是，序列\({g}\)中\(0\)到\(n-1\)每个数出现且恰好出现一次
当然，大小关系如同我们所学的那样是具有传递性的
现在我们有能力每次交换序列\({g}\)中的两个数，即\(swap(g_x,g_y)\)
问至少需要交换多少次才能保证这个序列\({a}\)中所有数相等

输入格式

第一行一个数\(n\)，表示序列长度
第二行\(n\)个数，表示序列\({g}\)

输出格式

一个数表示不同数值的数目

样例输入1

4
1 2 3 0

样例输出1

0

样例输入2

4
1 0 2 3

样例输出2

2

数据规模

对于20%的数据有
\(n\leq20\)
对于50%的数据有
\(n\leq1000\)
对于70%的数据有
\(n\leq20000\) 对于100%的数据有
\(n\leq100000\)

zqy2018's solution

/*
    Hint: Disjoint set
*/
#include <cstdio>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, g[100005], fa[100005], siz[100005], tot;
int Find(int x){
    return (fa[x] == x ? x: (fa[x] = Find(fa[x])));
}
void Union(int x, int y){
    int u = Find(x), v = Find(y);
    if (u == v) return ;
    if (siz[u] < siz[v])
        fa[u] = v, siz[v] += siz[u];
    else 
        fa[v] = u, siz[u] += siz[v];
    --tot;
}
void init(){
    n = read();
    tot = n;
    for (int i = 1; i <= n; ++i)
        fa[i] = i, siz[i] = 1;
    for (int i = 1; i <= n; ++i)
        g[i] = read() + 1, Union(i, g[i]);
}
void solve(){
    printf("%d\n", tot - 1);
}
int main(){
    init();
    solve();
    return 0;
}