997. Find the Town Judge

📋 Đề Bài

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 for the town judge) trusts the town judge.
There is exactly one person that satisfies properties 1 and 2.

You are given an array trust where trust[i] = [a_i, b_i] representing that the person labeled a_i trusts the person labeled b_i.

Return the label of the town judge if the town judge exists and can be identified, or return -1 otherwise.

Example 1:

Input: n = 2, trust = [[1,2]]
Output: 2

Example 2:

Input: n = 3, trust = [[1,3],[2,3]]
Output: 3

Example 3:

Input: n = 3, trust = [[1,3],[2,3],[3,1]]
Output: -1

Constraints:

1 <= n <= 1000
0 <= trust.length <= 10⁴
trust[i].length == 2
All the pairs of trust are unique.
a_i != b_i
1 <= a_i, b_i <= n

🧠 Thuật Toán & Kỹ Thuật

Bit Manipulation (Thao tác bit)

⏱️ Thời gian O(n²)

💾 Không gian O(n)

💻 Lời Giải

C++ 0997-find-the-town-judge.cpp

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        vector<int> check(n + 1);
        const int inf = 1e9;
        
        for (auto t : trust) {
            check[t[0]] = inf;
            check[t[1]] += 1;
        }
        
        for (int i = 1; i <= n; ++i) {
            if (check[i] == n - 1) {
                return i;
            }
        }
        
        return -1;
    }
};