信息中继
基数环
本题其实是一个基数环问题,及一堆有向树合并到一个有向环上面,本题只有下面两种情况,可以发现陷入循环的点的所有点都是有父节点的,而没有陷入循环的点的最顶层父节点是没有父节点的,因此可以考虑用并查集来解决,但是要避免并查集形成环,即每次将点合并到最顶层根节点上
① $p[i]=f[i]$,合并的时候只合并到直接的父节点,不合并到根节点
② $p[i]=find(f[i])$,合并的时候每次都合并到最上次的根节点上
可以发现两种操作的不同仅在环处最后一次合并④处,如果合并到根节点,那么点5最后是合并到自己上,反之就是合并到直接的父节点,这样就会导致并查集死循环。所以含环的并查集在处理带环的问题的时候要将点合并到根节点上,避免并查集形成环
#include<bits/stdc++.h>
using namespace std;
int p[1010], f[1010], ans;
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
int n; cin >> n;
for (int i = 1; i <= n; i ++) p[i] = i;
for (int i = 1; i <= n; i ++)
{
cin >> f[i];
if (f[i]) p[i] = find(f[i]);
}
for (int i = 1; i <= n; i ++)
if (!f[find(i)]) ans ++;
cout << ans;
return 0;
}