最多邀请的个数

/*
 * Leetcode Problem 1820: Maximum Number of Invitations
 * 
 * Problem Description: Given an array of integers where each integer represents the index of another person that can be invited to a party, the task is to find the maximum number of people that can be invited such that no two people invite each other.
 * 
 * Approach using Java Streams:
 * 1. Convert the invitations array to a list of pairs representing the graph edges.
 * 2. Use Streams to process and find cycles and maximum path lengths.
 * 3. Combine the results to find the maximum number of invites.
 */

import java.util.*;
import java.util.stream.*;

public class MaxInvitationsStream {
    public int maximumInvitations(int[] favorite) {
        int n = favorite.length;
        List<Integer>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 0; i < n; i++) {
            graph[favorite[i]].add(i);
        }

        int[] dp = new int[n];
        boolean[] visited = new boolean[n];
        boolean[] inStack = new boolean[n];

        return IntStream.range(0, n).filter(i -> !visited[i]).map(i -> dfs(i, graph, dp, visited, inStack)).max().orElse(0);
    }

    private int dfs(int node, List<Integer>[] graph, int[] dp, boolean[] visited, boolean[] inStack) {
        if (visited[node]) {
            return dp[node];
        }
        visited[node] = true;
        inStack[node] = true;
        int maxLength = 1;

        for (int nextNode : graph[node]) {
            if (!visited[nextNode]) {
                maxLength = Math.max(maxLength, 1 + dfs(nextNode, graph, dp, visited, inStack));
            } else if (inStack[nextNode]) {
                maxLength = 0;  // Cycle detected
            }
        }

        dp[node] = maxLength;
        inStack[node] = false;
        return dp[node];
    }

    public static void main(String[] args) {
        MaxInvitationsStream mis = new MaxInvitationsStream();
        int[] favorite = {2, 2, 1, 2};
        System.out.println(mis.maximumInvitations(favorite));  // Output: 3
    }
}