Question 4 of leetcode 274 weekly competition maximum number of employees participating in the meeting

Meaning:

Give you an array of \ (favorite \) with subscripts from \ (0 \) ~ \ (n-1 \), \ (favorite [i] \) indicates that the subscript of the person you like \ (I \) is \ (favorite [i] \). Now there is a round table for you to arrange as many people as possible to attend the meeting. Make sure that at least one person on the left and right sides of each person is your favorite, and each person will only like one person, Ask how many people can attend the meeting at most.

Idea:

This problem can be transformed into a graph theory problem (directed graph). Suppose that some people's favorite people can form a ring, and everyone on the ring can meet the conditions - there is at least one person next to them who likes them. So we can first find the largest ring in the graph. The answer may be the number of points on the largest ring \ (cnt \). There is another case: assuming that two people like each other, we can find the longest chain of the two people's lovers. A binary ring plus two chains can also meet the conditions, and multiple such forms can also meet the conditions together. Therefore, we also need to calculate the number of participants \ (ans \) in all cases of binary ring plus two chains, The answer is \ (max(ans, cnt) \).

Inspection algorithm:

How to find the largest ring: first, use the idea of topological sorting to select the points that can form a ring, and find the largest ring in \ (dfs \).

How to find the two longest chains: you can use \ (dfs \) to search deeply, which requires reverse mapping. In this case, you will not find the ring, because reverse mapping points to the person you like, and each person you like will only like one person.

code:

const int N = 100010;
class Solution {
public:
    int du[N], h[N], e[N], ne[N], idx = 0, vis[N], h1[N], e1[N], ne1[N], idx1 = 0;
    bool st[N];
    int dfs(int index, vector<int>&favorite)//Search maximum ring
    {
        if(!vis[index])
        {
            vis[index] = true;
            return dfs(favorite[index], favorite) + 1;
        }
        return 0;
    }

    void add(int a,int b)//Forward mapping
    { 
        e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
    }

    void add1(int a,int b)//Reverse mapping
    { 
        e1[idx1] = b, ne1[idx1] = h1[a], h1[a] = idx1 ++;
    }

    int dfs1(int x)//Calculate the longest chain
    {
        int v = 0;
        for(int kk = h1[x]; kk != -1; kk = ne1[kk]) v = max(v, dfs1(kk));
        return v + 1;
    }
    int calc(int i, int j)//Calculate the maximum length of the two chains
    {
        int v = 0;
        for(int k = h1[i]; k != -1; k = ne1[k])
        {
            int x = e1[k];
            if(x != j)
            v = max(v, dfs1(x));
        }
        int w = 0;
        for(int k = h1[j]; k != -1; k = ne1[k])
        {
            int x = e1[k];
            if(x != i)
            w = max(w, dfs1(x));
        }
        return w + v;
    }

    int maximumInvitations(vector<int>& favorite) {
        int n = favorite.size();
        for(int i = 0; i < n; i ++ )
        {
            h[i] = -1;
            h1[i] = -1;
            st[i] = true;
            vis[i] = false;
        }
        for(int i = 0; i < n; i ++ )
        {
            add(i, favorite[i]);
            add1(favorite[i], i);
            du[favorite[i]] ++;
        }
        queue<int>q;
        for(int i = 0; i < n; i ++ )
            if(!du[i])
                q.push(i);
        while(!q.empty())//Topological sorting sifts out the points that can form a ring
        {
            int x = q.front();
            st[x] = false;
            q.pop();
            for(int i = h[x]; i != -1; i = ne[i])
            {
                int y = e[i];
                du[y] --;
                if(!du[y]) q.push(y);
            }
        }
        int cnt = 0;//Maximum length of ring
        for(int i = 0; i < n; i ++ ){
            if(!vis[i] && st[i])
                cnt = max(dfs(i, favorite), cnt);
        }
        //The length of the longest ring is cnt.
        //Next, the feasibility scheme of binary ring generation is required
        int ans = 0;
        for(int i = 0; i < n; i ++ )
        {
            if(favorite[favorite[i]] == i && favorite[i] > i)//The person I like is myself
            {
                ans += 2 + calc(i, favorite[i]);
            }
        }
        return max(ans, cnt);
    }
};