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:
You are given an array trust where trust[i] = [ai, bi] representing that the person labeled ai trusts the person labeled bi. If a trust relationship does not exist in trust array, then such a trust relationship does not exist.
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 <= 10000 <= trust.length <= 104trust[i].length == 2trust are unique.ai != bi1 <= ai, bi <= nprogram main
implicit none
integer :: n, i, j, k, m, n_people, n_trust, trust(n, n), trusted(n), &
untrusted(n), town_judge
! Examples
n = 2
trust = reshape([1, 2, 2, 1], shape=[n, n])
write(*, '(A, I0)') 'Example 1: ', solve(n, trust)
n = 3
trust = reshape([1, 3, 2, 3], shape=[n, n])
write(*, '(A, I0)') 'Example 2: ', solve(n, trust)
n = 3
trust = reshape([1, 3, 2, 3, 3, 1], shape=[n, n])
write(*, '(A, I0)') 'Example 3: ', solve(n, trust)
contains
function solve(n_people, trust) result(town_judge)
implicit none
integer, intent(in) :: n_people, trust(:, :)
integer :: i, j, k, m, trusted(n_people), untrusted(n_people)
town_judge = -1
! Initialize arrays
trusted = 0
untrusted = 0
! Count number of trust relationships
do i = 1, n_people
do j = 1, n_people
if (trust(i, j) > 0) then
trusted(j) = trusted(j) + 1
untrusted(i) = untrusted(i) + 1
end if
end do
end do
! Check if there is only one person who trusts nobody
m = count(untrusted == 0)
if (m == 1) then
town_judge = maxloc(untrusted, dim=1)
end if
! Check if there is only one person who is trusted by everybody
m = count(trusted == n_people - 1)
if (m == 1) then
town_judge = minloc(trusted, dim=1)
end if
end function solve
end program maintemp.f95:4:61:
4 | integer :: n, i, j, k, m, n_people, n_trust, trust(n, n), trusted(n), &
| 1
Error: Explicit shaped array with nonconstant bounds at (1)
temp.f95:22:54:
22 | function solve(n_people, trust) result(town_judge)
| 1
Error: Function result ‘town_judge’ at (1) has no IMPLICIT type
temp.f95:8:5:
8 | n = 2
| 1
Error: Symbol ‘n’ at (1) has no IMPLICIT type
temp.f95:9:9:
9 | trust = reshape([1, 2, 2, 1], shape=[n, n])
| 1
Error: Symbol ‘trust’ at (1) has no IMPLICIT type
module Judge
implicit none
private
public :: find_judge
contains
function find_judge(n, trust) result(judge)
integer, intent(in) :: n
integer, dimension(:, :), intent(in) :: trust
integer :: judge
logical, dimension(n) :: trusted
integer :: i, j, k
judge = -1
! Initialize the trusted array
trusted = .false.
! Loop through the trust relationships
do i = 1, size(trust, 1)
j = trust(i, 1)
k = trust(i, 2)
if (j == k) then
! Self-trust is not allowed
cycle
end if
trusted(j) = .true.
if (trusted(k)) then
! If someone is trusted by someone else, then they cannot be the judge
judge = -1
exit
end if
end do
! Check if there is only one person who is trusted by no one
do i = 1, n
if (.not. trusted(i)) then
judge = i
exit
end if
end do
end function find_judge
end module Judge
program test
use Judge
implicit none
integer :: n, i, j, k
integer, dimension(:, :), allocatable :: trust
integer :: judge
! Test case 1:
n = 2
allocate(trust(1, 2))
trust = reshape([1, 2, 2, 1], shape(trust))
judge = find_judge(n, trust)
if (judge /= 2) then
write (*, *) "Test case 1 failed"
stop
end if
! Test case 2:
n = 3
allocate(trust(2, 3))
trust = reshape([1, 3, 2, 3, 3, 1], shape(trust))
judge = find_judge(n, trust)
if (judge /= 3) then
write (*, *) "Test case 2 failed"
stop
end if
! Test case 3:
n = 3
allocate(trust(3, 3))
trust = reshape([1, 3, 2, 3, 3, 1], shape(trust))
judge = find_judge(n, trust)
if (judge /= -1) then
write (*, *) "Test case 3 failed"
stop
end if
! Test case 4:
n = 4
allocate(trust(4, 4))
trust = reshape([1, 3, 2, 4, 3, 4, 4, 1], shape(trust))
judge = find_judge(n, trust)
if (judge /= -1) then
write (*, *) "Test case 4 failed"
stop
end if
! Test case 5:
n = 5
allocate(trust(5, 5))
trust = reshape([1, 3, 2, 4, 5, 3, 4, 5, 4, 1], shape(trust))
judge = find_judge(n, trust)
if (judge /= -1) then
write (*, *) "Test case 5 failed"
stop
end if
! Test case 6:
n = 6
allocate(trust(6, 6))
trust = reshape([1, 3, 2, 4, 5, 6, 3, 4, 5, 6, 4, 1], shape(trust))
judge = find_judge(n, trust)
if (judge /= -1) then
write (*, *) "Test case 6 failed"
stop
end if
! Test case 7:
n = 7
allocate(trust(7, 7))
trust = reshape([1, 3,
temp.f95:114:26:
114 | trust = reshape([1, 3,
| 1
Error: Syntax error in array constructor at (1)
f951: Error: Unexpected end of file in ‘temp.f95’
def findJudge(n, trust):
trust_counts = [0] * (n + 1)
for a, b in trust:
trust_counts[a] -= 1
trust_counts[b] += 1
for i in range(1, n + 1):
if trust_counts[i] == n - 1:
return i
return -1
trustCounts to store the number of trusts for each person.trustCounts for the person who trusts (a), and increment the count for the person being trusted (b).trustCounts array and check if any person has a trust count equal to n - 1, as this would mean that everyone trusts that person (except for themselves).int findJudge(int n, vector<vector<int>>& trust) {
vector<int> trustCounts(n + 1, 0);
for (auto& t : trust) {
trustCounts[t[0]]--;
trustCounts[t[1]]++;
}
for (int i = 1; i <= n; i++) {
if (trustCounts[i] == n - 1)
return i;
}
return -1;
}
trustCounts to store the number of trusts for each person.trustCounts for the person who trusts (a), and increment the count for the person being trusted (b).trustCounts array and check if any person has a trust count equal to n - 1, as this would mean that everyone trusts that person (except for themselves).