aboutsummaryrefslogtreecommitdiff
path: root/max_employees_invited.c
blob: 1537ae4155e0394a3cbcfc348ca8721b3eeb8779 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
// 2127. Maximum Employees to Be Invited to a Meeting
#include "leetcode.h"

/*
 * a company is organising a meeting and has a list of 'n' employees, waiting to
 * be invited. they have arrange for a large circular table, capable of seating
 * any number of employees. the employees are numbered from 0 to 'n - 1'. each
 * employee has a favourite person and they will attend the meeting only if they
 * can sit next to their favourite person. the favourite person of an employee
 * is not themselves. given a 0 indexed integer array 'favorite' where
 * 'favorite[i]' denotes the favourite person of the i'th employee, return the
 * maximum number of employees that can be invited.
 */

void topo_sort(const int *favorite, int *indegrees, int *chain_lens, int *stack,
               int node_cnt) {
  int stack_idx = 0;
  for (int i = 0; i < node_cnt; i++)
    if (!indegrees[i])
      stack[stack_idx++] = i;
  while (stack_idx) {
    int node = stack[--stack_idx], nn = chain_lens[node],
        parent = favorite[node], pn = chain_lens[parent];
    if (pn <= nn)
      chain_lens[parent] = nn + 1;
    indegrees[parent]--;
    if (!indegrees[parent])
      stack[stack_idx++] = parent;
  }
}

int traverse(const int *favorite, int *unvis, const int *chain_lens,
             int node_cnt) {
  int largest = 0, sum = 0;
  for (int i = 0; i < node_cnt; i++) {
    if (!unvis[i])
      continue;
    int start = i, curr = i, cn = 0;
    do {
      unvis[curr] = 0;
      cn++;
      curr = favorite[curr];
    } while (curr != start);
    if (cn > 2)
      largest = fmax(largest, cn);
    else
      sum += chain_lens[curr] + chain_lens[favorite[curr]] + 2;
  }
  return fmax(largest, sum);
}

int dfs(int *favorite, int favoriteSize) {
  int *buf = (int *)malloc(3 * favoriteSize * sizeof(int));
  int *indegrees = buf;
  memset(indegrees, 0, favoriteSize * sizeof(int));
  int *chain_lens = indegrees + favoriteSize;
  memset(chain_lens, 0, favoriteSize * sizeof(int));
  int *stack = chain_lens + favoriteSize;
  for (int i = 0; i < favoriteSize; i++) {
    int parent = favorite[i];
    indegrees[parent]++;
  }
  topo_sort(favorite, indegrees, chain_lens, stack, favoriteSize);
  int ans = traverse(favorite, indegrees, chain_lens, favoriteSize);
  free(buf);
  return ans;
}

int maximumInvitations(int *favorite, int favoriteSize) {
  return dfs(&favorite[0], favoriteSize);
}

int main() {
  int f1[] = {2, 2, 1, 2}, f2[] = {1, 2, 0}, f3[] = {3, 0, 1, 4, 1};
  printf("%d\n", maximumInvitations(f1, ARRAY_SIZE(f1))); // expect: 3
  printf("%d\n", maximumInvitations(f2, ARRAY_SIZE(f2))); // expect: 3
  printf("%d\n", maximumInvitations(f3, ARRAY_SIZE(f3))); // expect: 4
}