BZOJ 1529: [POI2005]ska Piggy banks( 并查集 )

BZOJ 1529: [POI2005]ska Piggy banks( 并查集 )

每一连通块砸开一个就可以拿到所有的钱, 所以用并查集求连通块数

-------------------------------------------------------------------

#include<bits/stdc++.h>
  
#define rep(i, n) for(int i = 0; i < n; i++)
#define clr(x, c) memset(x, c, sizeof(x))
 
using namespace std;
 
const int maxn = 1000009;
 
int fa[maxn], n, ans;
 
int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
 
void unite(int x, int y) {
int a = find(x), b = find(y);
fa[a] = b;
ans -= a != b;
}
 
int main() {
freopen("test.in", "r", stdin);
cin >> n;
ans = n;
rep(i, n) fa[i] = i;
rep(i, n) {
int v;
scanf("%d", &v);
unite(--v, i);
}
cout << ans << "\n";
return 0;
}

-------------------------------------------------------------------

1529: [POI2005]ska Piggy banks

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 959  Solved: 437
[Submit][Status][Discuss]

Description

Byteazar 有 N 个小猪存钱罐. 每个存钱罐只能用钥匙打开或者砸开. Byteazar 已经把每个存钱罐的钥匙放到了某些存钱罐里. Byteazar 现在想买一台汽车于是要把所有的钱都取出来. 他想尽量少的打破存钱罐取出所有的钱,问最少要打破多少个存钱罐.

Input

第一行一个整数 N (1 <= N <= 1.000.000) – 表示存钱罐的总数. 接下来每行一个整数,第 i+1行的整数代表第i个存钱罐的钥匙放置的存钱罐编号.

Output

一个整数表示最少打破多少个存钱罐.

Sample Input

4
2
1
2
4

Sample Output

2
In the foregoing example piggy banks 1 and 4 have to be smashed.

HINT

Source

上一篇:单例-b


下一篇:Linux安装.net core