Skip to main content

Degree

In-degree and out-degree - how many edges point into and out of a node - are enough to answer a surprising range of graph questions without ever building an adjacency list or traversing an edge. Counting those two arrays over the raw edge list is the whole trick.

The definitions, the source/sink signal table, the handshake lemma and the self-check it gives you are on Graph Anatomy. This page is the practice set.

Sink & Source Identification​

Find the one node whose degree hits an exact target - 0 for a plain source/sink, or n - 1 for a node everyone else points at.

997. Find the Town Judge​

Easy·
2 Approaches
FIG. 997 FIND THE TOWN JUDGE DEGREE● INTERACTIVE
visualization loads as you reach it
class Solution:
def findJudge(self, n: int, trust: List[List[int]]) -> int:
in_degree = [0 for i in range(n + 1)]
out_degree = [0 for i in range(n + 1)]
for a, b in trust:
out_degree[a] += 1
in_degree[b] += 1
for node in range(1, n + 1):
if in_degree[node] == n - 1 and out_degree[node] == 0:
return node
return -1

1436. Destination City​

Easy·
FIG. 1436 DESTINATION CITY OUT DEGREE● INTERACTIVE
visualization loads as you reach it
class Solution:
def destCity(self, paths: List[List[str]]) -> str:
out_degree = {}
for a, b in paths:
out_degree[a] = out_degree.get(a, 0) + 1
out_degree[b] = out_degree.get(b, 0)
for i, j in out_degree.items():
if j == 0:
return i
return ans

1557. Minimum Number of Vertices to Reach All Nodes​

Medium·
FIG. 1557 MIN VERTICES DEGREE● INTERACTIVE
visualization loads as you reach it
class Solution:
def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:
in_degree = [0] * (n)
result = []
for a, b in edges:
in_degree[b] += 1
for i in range(n):
if in_degree[i] == 0:
result.append(i)
return result

Greedy Elimination​

Both model "the one node everyone points at, that points at no one" - but instead of counting degrees, they walk the nodes once with a running candidate, discarding it whenever the current node disproves it. One survivor is left after a single pass.

2923. Find Champion I​

Easy·
2 Approaches
FIG. 2923 FIND CHAMPION I SCAN● INTERACTIVE
visualization loads as you reach it
class Solution:
def findChampion(self, grid: List[List[int]]) -> int:
n = len(grid)
in_degree = [0 for _ in range(n)]
for i in range(n):
for j in range(n):
if grid[i][j] == 1:
in_degree[i] += 1
for i, deg in enumerate(in_degree):
if deg == n - 1:
return i
return -1

277. Find the Celebrity​

Medium·
2 Approaches
FIG. 277 FIND THE CELEBRITY DEGREE● INTERACTIVE
visualization loads as you reach it
class Solution:
def findCelebrity(self, n: int) -> int:
in_degrees = [0] * (n + 1)
out_degrees = [0] * (n + 1)
for i in range(n):
for j in range(n):
if i == j:
continue
edge = knows(i, j)
in_degrees[j] += edge
out_degrees[i] += edge
for i in range(n):
if in_degrees[i] == n - 1 and out_degrees[i] == 0:
return i
return -1

Degree Arithmetic​

Combine degrees across multiple nodes, correcting for edges shared between them.

1615. Maximal Network Rank​

Medium·
FIG. 1615 MAXIMAL NETWORK RANK● INTERACTIVE
visualization loads as you reach it
class Solution:
def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
degree = [0] * n
adj_list = collections.defaultdict(set)
maxi = 0
for a, b in roads:
degree[a] += 1
degree[b] += 1
adj_list[a].add(b)
adj_list[b].add(a)
 
for a in range(n):
for b in range(n):
if a == b:
continue
total = degree[a] + degree[b] - (b in adj_list[a])
maxi = max(maxi, total)
return maxi