[Title Description]

Force bucklehttps://leetcode-cn.com/problems/maximum-employees-to-be-invited-to-a-meeting/

A company is going to organize a meeting with n# employees on the invitation list. The company has prepared a round table for any number of employees.

Employee numbers are 0} to n - 1. Each employee has an employee who likes ， and each employee will attend the meeting only if ， he is arranged next to the employee he likes. The employee that every employee likes will not be himself.

Give you an integer array {favorite with subscript starting from 0}, where {favorite[i] represents the employee liked by the {I} employee. Please return to the maximum number of employees attending the meeting.

 

Example 1:

Input: favorite = [2,2,1,2]
Output: 3
Explanation:
The figure above shows the company inviting employees 0, 1 and 2 to the meeting and their seats at the round table.
It is impossible to invite all employees to the meeting because employee 2 cannot sit next to employees 0, 1 and 3 at the same time.
Note that the company can also invite employees 1, 2 and 3 to the meeting.
Therefore, the maximum number of employees participating in the meeting is 3.
Example 2:

Input: favorite = [1,2,0]
Output: 3
Explanation:
Every employee is at least another employee's favorite employee. So the company invited all of them to the meeting on the premise that all of them attended the meeting.
The seating arrangement is as shown in Figure 1:
-Employee 0 sits between employee 2 and 1.
-Employee 1 sits between employees 0 and 2.
-Employee 2 sits between employees 1 and 0.
The maximum number of employees participating in the meeting is 3.
Example 3:

 

Input: favorite = [3,0,1,4,1]
Output: 4
Explanation:
The figure above shows that the company can invite employees 0, 1, 3 and 4 to the meeting and their seats on the round table.
Employee 2 cannot attend because the seat next to employee 0 he likes has been occupied.
So the company can only not invite employees 2.
The maximum number of employees participating in the meeting is 4.
 

Tips:

n == favorite.length
2 <= n <= 105
0 <= favorite[i] <= n - 1
favorite[i] != i

[Title Analysis]

By I pointing to fav[i], we can construct a directed graph with n nodes and N edges, and the degree of each node is 1;

There may be multiple connected domains in the graph, and each connected domain has only one ring. There is no case without a ring (because there are n nodes and N edges);

For the size of the ring (the number of nodes in the ring), each connected domain has the following two cases:

1. The size of the ring is equal to 2, and two chains end at the vertex of the ring;

For example, 0 - > 1 - > 2 < - > 3 - > 4 - > 5 can participate in the round table at the same time. At this time, the maximum number of participants is the sum of the lengths of the two longest chains;

2. If the length of the ring is greater than 2, the isolated vertex (in degree 0) or chain (in degree 0 at the end of the chain) connected to the vertex of the ring cannot participate in the round table, then the maximum number of participants in the meeting is the size of the maximum ring;

As shown in Figure 5 and 6, you can't attend the meeting

        0->1->2

        |         |

        4<----3->5->6

Based on the above analysis, the algorithm design is as follows:

1. DFS can be used to find the length of the ring, starting from a point on the ring;

How to determine whether it is a point on the ring? Topological sorting can be adopted. If the penetration is not 0, it is the point on the ring;

2. For the scenario where the length of the ring is equal to 2, reverse the length of the chain;

In this scenario, it should be noted that there may be multiple chains in the figure, each chain is a legal result, and the final number of people is the sum of all the longest chains;

[Code]

class Solution {
public:
/*
    By I pointing to fav[i], we can construct a directed graph with n nodes and N edges, and the degree of each node is 1;
    There may be multiple connected domains in the graph, and each connected domain has only one ring. There is no case without a ring (because there are n nodes and N edges);
    For the size of the ring (the number of nodes in the ring), each connected domain has the following two cases:
    1,The size of the ring is equal to 2, and two chains end at the vertex of the ring;
    For example, 0 - > 1 - > 2 < - > 3 - > 4 - > 5 can participate in the round table at the same time. At this time, the maximum number of participants is the sum of the lengths of the two longest chains;

    2,If the length of the ring is greater than 2, the isolated vertex (in degree 0) or chain (in degree 0 at the end of the chain) connected to the vertex of the ring cannot participate in the round table, then the maximum number of participants in the meeting is the size of the maximum ring;
    As shown in Figure 5 and 6, you can't attend the meeting
        0->1->2
        |     |
        4<----3->5->6
    Based on the above analysis, the algorithm design is as follows:
    1,DFS can be used to find the length of the ring, starting from a point on the ring;
    How to determine whether it is a point on the ring? Topological sorting can be adopted. If the penetration is not 0, it is the point on the ring;
    2,For the scene where the length of the ring is equal to 2, reverse the length of the chain;
    In this scenario, it should be noted that there may be multiple chains in the figure, each chain is a legal result, and the final number of people is the sum of all the longest chains;
*/
    int maximumInvitations(vector<int>& favorite) {
        int res= 0;
        unordered_map<int, vector<int>> g;
        unordered_map<int, vector<int>> rg;// Record the reverse connection relationship in order to traverse the length of the chain

        int len = favorite.size();
        vector<int> inDegree(len, 0);
        for (int i = 0; i < len; ++i) {
            inDegree[favorite[i]]++;
            g[i].emplace_back(favorite[i]);
            rg[favorite[i]].emplace_back(i);
        }
        // Topology sorting to obtain nodes on the ring
        queue<int> q;
        for (int i = 0; i < len; ++i) {
            if (inDegree[i] == 0) {
                q.emplace(i);
            }
        }
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (auto& m : g[v]) {
                inDegree[m]--;
                if (inDegree[m] == 0) {
                    q.emplace(m);
                }
            }
        }
        
        // DFS traversal ring
        vector<int> circle;
        vector<bool> visited(len, false);
        function<void(int)> DFS = [&](int v) {
            visited[v] = true;
            circle.emplace_back(v);
            for (auto& m : g[v]) {
                if (!visited[m] && inDegree[m] != 0) {
                    DFS(m);
                }
            }
        };
        // When the size of the ring is equal to 2, traverse the chain in reverse to obtain the length of the chain;
        // [v,w] is the two ends of the ring, starting from v, traversing backward and excluding W;
        // Starting from w, reverse traversal, excluding v;
        int maxDepth = 0;
        function<void(int, int, int)> DFS2 = [&](int v, int w, int depth) {
            maxDepth = max(maxDepth, depth);
            for (auto& m : rg[v]) {
                if (m != w) {
                    DFS2(m, w, depth + 1);
                }
            }
        };

        int sumChainLen = 0;
        for (int i = 0; i < len; ++i) {
            if (inDegree[i] != 0 && !visited[i]) {
                circle.resize(0);
                DFS(i);
                int circleLen = circle.size();
                if (circleLen == 2) {
                    maxDepth = 0;
                    DFS2(circle[0], circle[1], 1);
                    sumChainLen += maxDepth;
                    maxDepth = 0;
                    DFS2(circle[1], circle[0], 1);
                    sumChainLen += maxDepth;
                } else {
                    res = max(res, circleLen);
                }
            }
        }
        return max(res, sumChainLen);
    }
};