aboutsummaryrefslogtreecommitdiff
path: root/other/find_town_judge.cpp
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-03-10 00:36:13 -0600
committerJack Sangdahl <[email protected]>2025-03-10 00:36:13 -0600
commit7c60dee83b436e8e8a667bf9f191beced8de4fc3 (patch)
treeeb7a24ee2067f92245c57bb118e85a1baf15df50 /other/find_town_judge.cpp
parent5d7cdc215e4ba1ec4cbb24c084cccb5e5e641468 (diff)
downloadleetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.tar.gz
leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.zip
chore: move cpp and rust code to directory
Diffstat (limited to 'other/find_town_judge.cpp')
-rw-r--r--other/find_town_judge.cpp46
1 files changed, 46 insertions, 0 deletions
diff --git a/other/find_town_judge.cpp b/other/find_town_judge.cpp
new file mode 100644
index 0000000..5607688
--- /dev/null
+++ b/other/find_town_judge.cpp
@@ -0,0 +1,46 @@
+// 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.
+ */
+
+class Solution {
+public:
+ int findJudge(int n, vvd trust) {
+ vector<unordered_set<int>> graph(n + 1, unordered_set<int>());
+ for (auto &edge : trust) {
+ int a = edge[0], b = edge[1];
+ graph[a].insert(b); // a trusts b
+ }
+ int townJudge = -1;
+ for (int i = 1; i <= n; ++i)
+ if (graph[i].size() == 0) {
+ townJudge = i;
+ break;
+ }
+ if (townJudge == -1)
+ return -1;
+ for (int i = 1; i <= n; ++i) {
+ if (i == townJudge)
+ continue;
+ if (!graph[i].count(townJudge))
+ return -1;
+ }
+ return townJudge;
+ }
+};
+
+int main() {
+ Solution obj;
+ vvd trust1 = {{1, 2}}, trust2 = {{1, 3}, {2, 3}},
+ trust3 = {{1, 3}, {2, 3}, {3, 1}};
+ cout << obj.findJudge(2, trust1) << endl; // expect: 2
+ cout << obj.findJudge(3, trust2) << endl; // expect: 3
+ cout << obj.findJudge(3, trust3) << endl; // expect: -1
+}