AcWing 1977. Information relay (base ring tree, parallel search set)

【 Title Description 】
Farmer John has $N$ A cow , Number $1\sim N$.
A home-made telephone made of cans and ropes , They will communicate with each other when John is not paying attention .
Each cow can forward messages to another cow at most ：
For cows $i$, It will forward any information it receives to the cow $F_i$（$F_i$ And $i$ It must be different ）.
If $F_i$ by $0$, Then cow $i$ Do not forward messages .
Unfortunately , Cows realize that news from some cows may eventually fall into a cycle , Constantly being forwarded .
Please make sure how many cows out of all cows send messages that won't fall into a cycle forever .

【 Input format 】
The first line contains integers $N$.
Next $N$ That's ok , Each line contains an integer $F_i$.

【 Output format 】
Output the number of cows that send messages that will not fall into a loop .

【 Data range 】
$1\le N\le 1000$
$0\le F_i\le N$

【 sample input 】

5
0
4
1
5
4

【 sample output 】

2

【 Sample explanation 】
cow $1$ Don't send any messages , So it won't fall into a cycle .
cow $3$ Send a message to the cow $1$, So it won't fall into a cycle .
The messages sent by the other three cows will fall into a cycle .

【 analysis 】

---

Because each cow can only forward one message to another cow at most , Therefore, the maximum output of each point is $1$. So the graph is composed of several base ring trees （ Every point has a degree ） And some ordinary trees （ The degree of $0$ The point of is the root node ）, As shown in the figure below ：

One of the solutions to this problem is to find the number of points that can go to a certain ring $cnt$, Total points minus $cnt$ Is the answer . For judging whether each point can go to the ring , have access to set, Go straight from the current point , Save all the points passed into set in , If you reach the exit degree of $0$ The point of the note will not go to the ring , If you get there, you are already set In the point , It shows that a ring is formed . The time complexity of this solution is $O(n^2)$.

Another solution is to search the set by union , For a point $i$, If it points to another point $j$, So let's connect these two points , Due to the direction limitation , So let $pre[find(i)]=find(j)$, In this way, if it is an ordinary tree, the root node of this set is with an outgoing degree of $0$ The point of . Finally, we traverse each point , If the outgoing degree of the root node is $0$, It shows that this point is in the ordinary tree , That is, they will not go to the ring , Add one... To the answer .

---

【$O(n^2)$ Code 】

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>
using namespace std;

const int N = 1010;
int to[N];
int n, res;//res Indicates the number of points that can reach the ring 

int main()
{
    
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> to[i];
    for (int i = 1; i <= n; i++)
    {
    
        unordered_set<int> st;
        for (int j = i; to[j]; j = to[j])
        {
    
            if (st.count(j)) {
     res++; break; }
            st.insert(j);
        }
    }
    cout << n - res << endl;
    return 0;
}

【$O(n)$ Code 】

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1010;
int pre[N], to[N];
int n, res;

int find(int k)
{
    
    if (pre[k] == k) return k;
    return pre[k] = find(pre[k]);
}

int main()
{
    
    cin >> n;
    for (int i = 1; i <= n; i++) pre[i] = i;
    for (int i = 1; i <= n; i++)
    {
    
        cin >> to[i];
        if (to[i]) pre[find(i)] = find(to[i]);
    }
    for (int i = 1; i <= n; i++)
        if (!to[find(i)]) res++;
    cout << res << endl;
    return 0;
}