There is an undirected star graph consisting of n nodes labeled from 1 to n. A star graph is a graph where there is one center node and exactly n - 1 edges that connect the center node with every other node.
You are given a 2D integer array edges where each edges[i] = [ui, vi] indicates that there is an edge between the nodes ui and vi. Return the center of the given star graph.
Example 1:
Input: edges = [[1,2],[2,3],[4,2]] Output: 2 Explanation: As shown in the figure above, node 2 is connected to every other node, so 2 is the center.
Example 2:
Input: edges = [[1,2],[5,1],[1,3],[1,4]] Output: 1
Constraints:
3 <= n <= 105edges.length == n - 1edges[i].length == 21 <= ui, vi <= nui != viedges represent a valid star graph.program main
implicit none
integer, parameter :: n = 5
integer, dimension(n-1) :: edges
integer :: i, j, k, center
! Example 1
edges = reshape([1, 2, 4, 2], shape=[n-1])
write (*, '(A, I0)') 'Example 1: ', find_center(edges)
! Example 2
edges = reshape([1, 2, 5, 1, 1, 3, 1, 4], shape=[n-1])
write (*, '(A, I0)') 'Example 2: ', find_center(edges)
contains
function find_center(edges) result(center)
implicit none
integer, intent(in) :: edges(:)
integer :: center
logical, allocatable :: visited(:)
integer :: i, j, k
allocate(visited(size(edges)))
visited = .false.
do i = 1, size(edges)
if (.not. visited(edges(i))) then
call dfs(edges, edges(i), visited)
end if
end do
center = 0
do i = 1, size(edges)
if (visited(edges(i))) then
center = edges(i)
exit
end if
end do
contains
recursive subroutine dfs(edges, node, visited)
implicit none
integer, intent(in) :: edges(:)
integer, intent(in) :: node
logical, intent(inout) :: visited(:)
integer :: i
visited(node) = .true.
do i = 1, size(edges)
if ((edges(i) /= node).and..not. visited(edges(i))) then
call dfs(edges, edges(i), visited)
end if
end do
end subroutine dfs
end function find_center
end program maintemp.f95:42:12:
42 | contains
| 1
Error: CONTAINS statement at (1) is already in a contained program unit
temp.f95:45:25:
45 | implicit none
| 1
Error: Duplicate IMPLICIT NONE statement at (1)
temp.f95:46:40:
46 | integer, intent(in) :: edges(:)
| 1
Error: Symbol ‘edges’ at (1) already has basic type of INTEGER
temp.f95:47:39:
47 | integer, intent(in) :: node
| 1
Error: Unexpected data declaration statement at (1)
temp.f95:48:45:
48 | logical, intent(inout) :: visited(:)
| 1
Error: Symbol ‘visited’ at (1) already has basic type of LOGICAL
temp.f95:49:24:
49 | integer :: i
| 1
Error: Symbol ‘i’ at (1) already has basic type of INTEGER
temp.f95:59:11:
59 | end subroutine dfs
| 1
Error: Expecting END FUNCTION statement at (1)
temp.f95:51:24:
51 | visited(node) = .true.
| 1
Error: Symbol ‘node’ at (1) has no IMPLICIT type
module StarGraph
implicit none
contains
function find_center(edges) result(center)
integer, intent(in) :: edges(:, :)
integer :: center, i, j, ui, vi
! Initialize the center to 1
center = 1
! Loop through all edges
do i = 1, size(edges, 1)
ui = edges(i, 1)
vi = edges(i, 2)
! If the edge connects the center to another node, update the center
if (ui == center .or. vi == center) then
center = ui
if (ui /= center) then
center = vi
end if
end if
end do
end function find_center
end module StarGraph
program test_star_graph
use StarGraph
implicit none
integer, parameter :: n = 5
integer :: edges(n - 1, 2) = reshape([1, 2, 2, 3, 4, 2], shape(edges))
integer :: center
! Test case 1
center = find_center(edges)
if (center /= 2) then
write (*, *) "Test case 1 failed. Expected center = 2, got ", center
stop 1
end if
! Test case 2
edges = reshape([1, 2, 5, 1, 1, 3, 1, 4], shape(edges))
center = find_center(edges)
if (center /= 1) then
write (*, *) "Test case 2 failed. Expected center = 1, got ", center
stop 1
end if
! Test case 3
edges = reshape([1, 2, 3, 4, 5, 6], shape(edges))
center = find_center(edges)
if (center /= 2) then
write (*, *) "Test case 3 failed. Expected center = 2, got ", center
stop 1
end if
! Test case 4
edges = reshape([1, 2, 3, 4, 5, 6, 7], shape(edges))
center = find_center(edges)
if (center /= 3) then
write (*, *) "Test case 4 failed. Expected center = 3, got ", center
stop 1
end if
! Test case 5
edges = reshape([1, 2, 3, 4, 5, 6, 7, 8], shape(edges))
center = find_center(edges)
if (center /= 4) then
write (*, *) "Test case 5 failed. Expected center = 4, got ", center
stop 1
end if
! Test case 6
edges = reshape([1, 2, 3, 4, 5, 6, 7, 8, 9], shape(edges))
center = find_center(edges)
if (center /= 5) then
write (*, *) "Test case 6 failed. Expected center = 5, got ", center
stop 1
end if
! Test case 7
edges = reshape([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], shape(edges))
center = find_center(edges)
if (center /= 6) then
write (*, *) "Test case 7 failed. Expected center = 6, got ", center
stop 1
end if
! Test case 8
edges = reshape([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], shape(edges))
center = find_center(edges)
if (center /= 7) then
write (*, *) "Test case 8 failed. Expected center = 7, got ", center
stop 1
end if
! Test case 9
edges = reshape([1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
temp.f95:40:37:
40 | integer :: edges(n - 1, 2) = reshape([1, 2, 2, 3, 4, 2], shape(edges))
| 1
Error: Without padding, there are not enough elements in the intrinsic RESHAPE source at (1) to match the shape
temp.f95:107:47:
107 | edges = reshape([1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
| 1
Error: Syntax error in array constructor at (1)
f951: Error: Unexpected end of file in ‘temp.f95’
def maximum_wealth(accounts):
return max(sum(customer) for customer in accounts)
Iterate through each customer's accounts in the grid. For each customer, calculate the total wealth by summing the values of all their bank accounts. Compare the total wealth of each customer with the previously calculated maximum wealth, and set the maximum wealth to the current customer's wealth if it is greater. Continue this process for all customers and return the final maximum wealth value when finished.
The implementations in C++, Java, and JavaScript use loops or built-in functions to iterate through the grid and calculate the sums. Python uses a small one-liner to achieve the same result with a generator expression.
int maximumWealth(vector<vector<int>>& accounts) {
int max_wealth = 0;
for (const auto& customer : accounts) {
max_wealth = max(max_wealth, accumulate(customer.begin(), customer.end(), 0));
}
return max_wealth;
}
Iterate through each customer's accounts in the grid. For each customer, calculate the total wealth by summing the values of all their bank accounts. Compare the total wealth of each customer with the previously calculated maximum wealth, and set the maximum wealth to the current customer's wealth if it is greater. Continue this process for all customers and return the final maximum wealth value when finished.
The implementations in C++, Java, and JavaScript use loops or built-in functions to iterate through the grid and calculate the sums. Python uses a small one-liner to achieve the same result with a generator expression.