[Blue Bridge Cup] children's worship circle

Children worship circle

Class $N$ Two children , Everyone has one of their favorite children （ You can also be yourself ）.

In a game , We need children to sit in a circle , Every child has his favorite child on his right side .

How many people can satisfy the circle ？

The children's number is $1,2,3,\cdots N$.

Input description
Enter the first line , An integer $N（3<N<10^5）$

Next line $N$ It's an integer , Separated by spaces .

Output description
An integer is required , Represents the number of people in the largest circle that satisfies the condition .

I/o sample
Example
Input

9
3 4 2 5 3 8 4 6 9

Output

4

Sample explanation

As shown in the figure below , Worship relations are indicated by arrows , Red means not in the circle .

obviously , The biggest circle is $[2453]$ The circle formed .

Ideas

• The problem can be transformed into the problem of finding the maximum number of sides of a cycle in a directed graph
• Each child is regarded as a node , The worship relationship is regarded as a directed side , So if there is $N$ Two children , Then there will be $N$ Nodes ,$N$ The strip has a directed edge
• For each node , It can be observed that ： There is and only one edge , If you want to form a circle , There must be an entry edge , Then we can see ： A node without an edge must not be a node in a circle
• At the beginning, first remove the incoming edge as $0$ The node of , Don't consider , So easy to know , The remaining nodes must form several circles
• $dfs$： There are two parameters , One is the $i$ Two children , One is the $i$ A child worshipped by children
• If these two children are the same , Then it must have formed a circle , Then this condition can be used as a recursive exit
• If these two children are different , Continued to $dfs$ , Until these two children are the same ( The initialized data has been guaranteed )
• Set the maximum number of sides of a circle , If a $dfs$ The number of sides found is greater than this maximum , Update
• Finally, output the maximum value

The code is as follows

#include <iostream>
#include <vector>
using namespace std;

vector<int> a;// Children array , The first i Children worship the first a[i] Two children 
vector<bool> vis;// Have you been visited 
vector<bool> flag;// Whether there is an edge 
int max_circle;// The maximum number of edges 
int circle;// Temporary variable , Reduce recursion overhead 
int n;// The number of children 

void init() {
    
    scanf("%d", &n);
    a.resize(n + 1);
    vis.resize(n + 1, false);
    flag.resize(n + 1, false);
    for (int i = 1; i <= n; i++) {
    
        scanf("%d", &a[i]);
        flag.at(a[i]) = true;// True means there is an edge , Otherwise no 
    }
}

void dfs(int start_id, int next_id) {
    
    if (next_id == start_id) {
    
        max_circle = max(circle, max_circle);
        return;
    }
    vis.at(next_id) = true;
    circle++;
    dfs(start_id, a.at(next_id));
}

void solve() {
    
    for (int i = 1; i <= n; i++) {
    
        if (flag.at(i) && !vis.at(i)) {
    
            vis.at(i) = true;
            circle = 1;
            dfs(i, a.at(i));
        }
    }
    printf("%d\n", max_circle);
}

int main(void) {
    
    init();
    solve();
    return 0;
}