fax 表示 x 可以 fax 拷贝。
更多细节见代码:
代码注释会有一些关于树的习惯叫法,请勿带入题目。
// byLuoguUID : 1013950
// submitPID : P2835
#include <bits/stdc++.h>
using namespace std;
int fa[205], n;
void init() {
for (int x = 1; x <= n; x++) {
fa[x] = x;
}
}
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y) {
fa[x] = y; // 因为x的祖先不一定能从y的祖先拷贝数据,但是x一定能从y拷贝数据。
// 把 fa[x] 改成 y,一定是不劣的,因为不管怎么样他都可以拷贝别人的数据,从谁那里拷贝就不重要了。
}
int main() {
cin >> n;
init();
for (int i = 1; i <= n; i++) {
while (true) {
int tmp;
cin >> tmp;
if (tmp == 0) break;
if (find(tmp) != find(i)) merge(tmp, i);
}
}
for (int i = 1; i <= n; i++) {
find(i); // 压缩路径,把每个人的父亲都变成祖先
}
sort(fa+1, fa+n+1);
int ans = 0, now_fa = 0;
for (int i = 1; i <= n; i++) {
if (fa[i] != now_fa) {
now_fa = fa[i];
ans++;
}
}
cout << ans << endl;
return 0;
}