diff options
author | Jack Sangdahl <[email protected]> | 2025-03-10 00:36:13 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-03-10 00:36:13 -0600 |
commit | 7c60dee83b436e8e8a667bf9f191beced8de4fc3 (patch) | |
tree | eb7a24ee2067f92245c57bb118e85a1baf15df50 /other/find_town_judge.cpp | |
parent | 5d7cdc215e4ba1ec4cbb24c084cccb5e5e641468 (diff) | |
download | leetcode-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.cpp | 46 |
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 +} |