Show problems as
Classic problem #1791EasyGraph Theory

Find Center of Star Graph

Real-world version: Hub Depot of the Courier Network
Tracked in this browser only
Read Find Center of Star Graph on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A courier company runs n depots labelled 1 through n. One of them is the hub: every other depot is joined to the hub by its own road, and there are no other roads, so the network holds exactly n - 1 roads and each road has the hub at one end.

roads lists those roads in no particular order. roads[i] = [a, b] records a road running between depot a and depot b, and the two ends of a road are always different depots.

Return the label of the hub depot.

Examples

Example 1

Input
roads = [[4, 2], [3, 4], [4, 5], [1, 4]]
Output
4

There are four roads, so the network has five depots. Depot `4` is written on every road, and no other depot is.

Example 2

Input
roads = [[9, 7], [7, 2], [7, 10], [1, 7], [7, 5], [3, 7], [7, 8], [6, 7], [7, 4]]
Output
7

Nine roads means ten depots. Depot `7` shares a road with each of the other nine depots, and every road listed has `7` on one side.

Example 3

Input
roads = [[1, 3], [2, 3]]
Output
3

The smallest network of this shape has three depots and two roads. Depot `3` appears on both roads.

Constraints

  • 3 <= n <= 10^5
  • roads.length == n - 1
  • roads[i].length == 2
  • 1 <= a, b <= n
  • a != b
  • The roads describe a network of the shape above, so a hub always exists.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def hub_depot(roads: list[list[int]]) -> int:
Java
public int hubDepot(int[][] roads)

More on the same topics