每一连通块砸开一个就可以拿到所有的钱, 所以用并查集求连通块数
-------------------------------------------------------------------
#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 << "
";
return 0;
}
-------------------------------------------------------------------
1529: [POI2005]ska Piggy banks
Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 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
2
1
2
4
Sample Output
2
In the foregoing example piggy banks 1 and 4 have to be smashed.