aboutsummaryrefslogtreecommitdiff
path: root/find_all_people_secret.c
blob: 578799d592c9cfc4cd66b97230c96d16f49a927b (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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
// 2092. Find All People With Secret
#include "leetcode.h"

/*
 * given an integer 'n' indicating there are 'n' people numbered from 0 to 'n -
 * 1'. you are also given a 0-indexed 2d integer array 'meetings' where
 * 'meetings[i] = [x_i, y_i, time_i]' indicates that person 'x_i'  and person
 * 'y_i' have a metting at 'time_i'. a person may attend multiple meetings at
 * the same time. finally, you are given an integer 'firstPerson'. person 0 has
 * a secret and initially shares the secret with a person 'firstPerson' at time
 * 0. this secret is then shared every time a meeting takes place with a person
 * that has the secret. more formall, for every meeting 'x_i', has secret at
 * 'time_i' then they will share the secret with person 'y_i' and vice versa
 */

int cmp(const void **a, const void **b) {
  if ((*(int **)a)[2] == (*(int **)b)[2])
    return (*(int **)a)[0] - (*(int **)b)[0];
  return (*(int **)a)[2] - (*(int **)b)[2];
}

void check(int *list, int a, int b, int i, int *returnSize, int *ans, int *time,
           int *timecount) {
  if (list[a] - list[b] == 1) {
    list[b]++;
    ans[*returnSize] = b;
    *returnSize += 1;
  } else if (list[b] - list[a] == 1) {
    list[a]++;
    ans[*returnSize] = a;
    *returnSize += 1;
  } else if (list[b] == 0 && list[a] == 0) {
    time[*timecount] = i;
    *timecount += 1;
  }
}

void sametime(int **meetings, int *ans, int *returnSize, int *time,
              int timecount, int *list) {
  int count = 1, newtimecount;
  while (count) {
    int copy = *returnSize;
    newtimecount = 0;
    for (int i = 0; i < timecount; i++) {
      check(list, meetings[time[i]][0], meetings[time[i]][1], time[i],
            returnSize, ans, time, &newtimecount);
    }
    count = *returnSize - copy;
    if (count == 0) {
      break;
    }
    copy = *returnSize;
    timecount = newtimecount;
    newtimecount = 0;
    for (int i = timecount - 1; i >= 0; i--) {
      check(list, meetings[time[i]][0], meetings[time[i]][1], time[i],
            returnSize, ans, time, &newtimecount);
    }
    count = *returnSize - copy;
    timecount = newtimecount;
  }
}

int *findAllPeople(int n, int **meetings, int meetingsSize,
                   int *meetingsColSize, int firstPerson, int *returnSize) {
  int *list = calloc(n, sizeof(int));
  int *ans = malloc(sizeof(int) * n);
  int *time = malloc(sizeof(int) * n);
  int timecount = 0;
  *returnSize = 2;
  for (int i = 0; i < meetingsSize; i++) {
    if (meetings[i][0] > meetings[i][1]) {
      int a = meetings[i][1];
      meetings[i][1] = meetings[i][0];
      meetings[i][0] = a;
    }
  }
  qsort(meetings, meetingsSize, sizeof(int *), cmp);
  list[0]++;
  list[firstPerson]++;
  ans[0] = 0;
  ans[1] = firstPerson;
  for (int i = 0; i < meetingsSize; i++) {
    if (list[meetings[i][0]] - list[meetings[i][1]] == 1) {
      list[meetings[i][1]]++;
      ans[*returnSize] = meetings[i][1];
      *returnSize += 1;
    } else if (list[meetings[i][1]] - list[meetings[i][0]] == 1) {
      list[meetings[i][0]]++;
      ans[*returnSize] = meetings[i][0];
      *returnSize += 1;
    } else if (i + 1 < meetingsSize && meetings[i][2] == meetings[i + 1][2]) {
      timecount = 0;
      check(list, meetings[i][0], meetings[i][1], i, returnSize, ans, time,
            &timecount);
      i++;
      while (i + 1 < meetingsSize && meetings[i][2] == meetings[i + 1][2]) {
        check(list, meetings[i][0], meetings[i][1], i, returnSize, ans, time,
              &timecount);
        i++;
      }
      check(list, meetings[i][0], meetings[i][1], i, returnSize, ans, time,
            &timecount);
      sametime(meetings, ans, returnSize, time, timecount, list);
    }
  }
  free(list);
  free(time);
  return ans;
}

int main() {
  int m1[3][3] = {{1, 2, 5}, {2, 3, 8}, {1, 5, 10}},
      m2[3][3] = {{3, 1, 3}, {1, 2, 2}, {0, 3, 3}},
      m3[3][3] = {{3, 4, 2}, {1, 2, 1}, {2, 3, 1}};
  int *mcs1, *mcs2, *mcs3, *rs1, *rs2, *rs3;
  int *fap1 = findAllPeople(6, (int **)m1, 3, mcs1, 1, rs1);
  int *fap2 = findAllPeople(4, (int **)m2, 3, mcs2, 1, rs2);
  int *fap3 = findAllPeople(5, (int **)m3, 3, mcs3, 1, rs3);
  for (int i = 0; i < 5; i++)
    printf("%d ", fap1[i]);
  printf("\n");
  for (int i = 0; i < 3; i++)
    printf("%d ", fap2[i]);
  printf("\n");
  for (int i = 0; i < 5; i++)
    printf("%d ", fap3[i]);
  printf("\n");
}