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

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;
}

{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

{
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 ++ )
{
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);
}
};

Added by pugisback on Tue, 04 Jan 2022 04:38:59 +0200