leetcode

Leetcode Solutions (0x6A73)
git clone https://git.pngu.org/leetcode
Log | Files | Refs | Submodules | README

find_town_judge.c (1539B)

 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
// 997. Find the Town Judge
#include "leetcode.h"

/*
 * in a town, there are 'n' people labeled from 1 to 'n'. there is a rumor that
 * one of these people is secretly the town judge. if the town judge exists,
 * then: the town judge trusts nobody. everybody (except the judge) trusts the
 * judge. given: array 'trust' where 'trust[i]' = [ai, bi] representing the the
 * person labeled ai trusts the person labeled bi. return label of judge, if
 * they exist.
 */

int findJudge(int n, int **trust, int trustSize, int *trustColSize) {
  int candidate = -1;
  bool arr[n + 1];
  for (int i = 0; i <= n; i++)
    arr[i] = false;
  for (int i = 0; i < trustSize; i++)
    arr[trust[i][0]] = true;
  for (int i = 1; i <= n; i++)
    if (!arr[i]) {
      candidate = i;
      break;
    }
  if (candidate == -1)
    return -1;
  for (int i = 1; i <= n; i++)
    arr[i] = false;
  for (int i = 0; i < trustSize; i++)
    if (trust[i][1] == candidate)
      arr[trust[i][0]] = true;
  bool ans = true;
  for (int i = 1; i <= n; i++) {
    if (i == candidate)
      continue;
    ans &= arr[i];
  }
  return ans ? candidate : -1;
}

int main() {
  int trust1[][2] = {{1, 2}}, trustColSize1[] = {1};
  int trust2[][2] = {{1, 3}, {2, 3}}, trustColSize2[] = {2};
  int trust3[][2] = {{1, 3}, {2, 3}, {3, 1}}, trustColSize3[] = {3};
  printf("%d\n", findJudge(2, trust1, 1, trustColSize1)); // expect: 2
  printf("%d\n", findJudge(3, trust2, 2, trustColSize1)); // expect: 3
  printf("%d\n", findJudge(3, trust3, 3, trustColSize1)); // expect: -1
}