Build a Quadtree and Analyze a Graph

Solve the following two coding problems.

1. Build a quadtree from an image

You are given an N x N matrix of integers representing an image, where N is a power of 2. A quadtree node represents a square region of the image.

• If all values in the region are the same, the node should be a leaf storing that value.
• Otherwise, the node should be an internal node with exactly four children representing the region's:
  • top-left quadrant
  • top-right quadrant
  • bottom-left quadrant
  • bottom-right quadrant

Design the quadtree node structure and write a function that builds the quadtree for the input matrix.

2. Find nodes that always lead to terminal nodes

You are given a directed graph with nodes labeled from 0 to n - 1, represented as an adjacency list graph, where graph[i] contains all outgoing neighbors of node i.

• A terminal node is a node with no outgoing edges.
• A node is safe if every possible path starting from that node eventually ends at a terminal node.

Return all safe nodes in ascending order.

Build a Quadtree from an Image

Return a nested dictionary quadtree for an N x N matrix where uniform regions become leaves.

Examples

Example 1

Input: ([[1,1],[1,1]],)
Output: {'leaf': True, 'value': 1}

Explanation: Uniform leaf.

Example 2

Input: ([[1,0],[0,1]],)
Output: {'leaf': False, 'children': [{'leaf': True, 'value': 1}, {'leaf': True, 'value': 0}, {'leaf': True, 'value': 0}, {'leaf': True, 'value': 1}]}

Explanation: Four leaf children.

Hints

1. Model object-style prompts as arrays or operation streams when needed.
2. Handle empty and boundary cases before the main logic.

Eventual Safe Nodes in a Directed Graph

Return all nodes from which every path eventually reaches a terminal node.

Examples

Example 1

Input: ([[1,2],[2,3],[5],[0],[5],[],[]],)
Output: [2, 4, 5, 6]

Explanation: Classic safe nodes example.

Example 2

Input: ([[],[0],[1]],)
Output: [0, 1, 2]

Explanation: All nodes safe.

Hints

1. Model object-style prompts as arrays or operation streams when needed.
2. Handle empty and boundary cases before the main logic.