Implement transaction network queries

Problem

You are building a small in-memory library to track pairwise customer transactions and answer connectivity questions about who has transacted with whom.

Model each transaction as an interaction between exactly two customers (e.g., "Jim pays Pam"). Once two customers transact, they are considered directly connected. Treat the relationship as undirected (if A transacts with B, then B has transacted with A).

Design a class (e.g., Transactions) that supports the following capabilities.

---

Part 1 — Direct/indirect existence query ("ever transacted together")

Implement an operation to record a transaction between two customers, and a query:

• haveEverTransactedTogether(x, y) -> bool

Return true if and only if customers x and y have ever been part of the same connected component in the transaction graph at the time of the query (i.e., based on all transactions recorded so far).

Example

1. haveEverTransactedTogether(Jim, Pam) -> false
2. Record: Jim transacts with Pam
3. haveEverTransactedTogether(Jim, Pam) -> true
4. Record: Pam transacts with Michael
5. haveEverTransactedTogether(Michael, Jim) -> true (because Michael—Pam—Jim forms a connected component)

---

Part 2 — Full network query

Implement:

• findNetwork(person) -> list/set

A person’s network is everyone who is reachable from that person via one or more transactions (i.e., all nodes in the same connected component), excluding the person themself.

Example 1 (two disconnected components)

Transactions: (a,b), (b,c), (a,d), (d,e), (g,f)

• findNetwork(a) -> {b,c,d,e}
• findNetwork(g) -> {f}

Example 2 (loop)

Transactions: (a,b), (b,d), (d,c), (c,a)

• findNetwork(a) -> {b,c,d}

---

Part 3 — Network query with degree limit

Extend the previous method to accept a second parameter n:

• findNetwork(person, n) -> list/set

Return all customers within at most n degrees of separation from person, excluding person.

• Degree 1: direct transaction partners
• Degree 2: partners of partners, etc.

Example 1

Transactions: (a,b), (b,c), (a,d), (d,e), (g,f)

• findNetwork(a, 1) -> {b,d}
• findNetwork(g, 1) -> {f}

Example 2 (loop)

Transactions: (a,b), (b,d), (d,c), (c,a)

• findNetwork(a, 1) -> {b,c}

Example 3

Transactions: (a,b), (b,c), (c,d), (b,e), (c,f), (d,g), (f,g), (g,h)

• findNetwork(d, 2) -> {c,g,b,f,h}
• findNetwork(h, 3) -> {g,d,f,c}
• findNetwork(a, 1) -> {b}

---

Notes / expectations

• You may assume customer identifiers are strings.
• The class should support adding transactions over time and answering queries at any point.
• Clearly define any helper methods and choose appropriate data structures.
• Be careful about cycles and repeated visits when exploring the network.

Transaction Network — Part 1: Ever Transacted Together

You are building a small in-memory library to track pairwise customer transactions. Each transaction connects exactly two customers and the relationship is undirected (if A transacts with B, then B has transacted with A). Once two customers transact, they are directly connected, and connectivity is transitive through the transaction graph.

Given a list of transactions (each a 2-element pair [x, y]) recorded so far and two customers x and y, return True if and only if x and y are in the same connected component of the transaction graph (i.e., they have ever transacted together, directly or indirectly). Return False if either customer has never appeared in any transaction, or if they belong to different components.

Example

• Before any transaction: Jim and Pam -> False
• After Jim pays Pam: Jim and Pam -> True
• After Pam pays Michael: Michael and Jim -> True (Michael—Pam—Jim is one component)

A customer is trivially connected to themself if they appear in any transaction.

Constraints

• 0 <= number of transactions
• Each transaction is a pair of two customer identifiers (strings).
• The relationship is undirected.
• x and y may or may not have appeared in any transaction.
• A customer that appears in any transaction is connected to itself.

Hints

1. Connectivity that is transitive across many edges is the classic use case for a disjoint-set (Union-Find) structure, or you can BFS/DFS from x and check if y is reachable.
2. Union the two endpoints of every transaction, then two customers are connected iff find(x) == find(y).
3. Handle the case where a queried customer never appears in any transaction — they cannot be connected to anyone (return False), unless x == y and they appear.

Transaction Network — Part 2: Find Full Network

Building on the pairwise transaction graph from Part 1 (undirected edges given as a list of [x, y] pairs), implement findNetwork(person).

A person's network is everyone reachable from that person via one or more transactions — i.e., all other nodes in the same connected component, excluding the person themself.

Given transactions and a person, return the network as a sorted list of distinct customer identifiers. If the person never appears in any transaction, return an empty list.

Example 1 (two disconnected components) Transactions: (a,b), (b,c), (a,d), (d,e), (g,f)

• findNetwork(a) -> ['b', 'c', 'd', 'e']
• findNetwork(g) -> ['f']

Example 2 (cycle) Transactions: (a,b), (b,d), (d,c), (c,a)

• findNetwork(a) -> ['b', 'c', 'd']

Constraints

• 0 <= number of transactions
• Each transaction is an undirected pair of customer identifiers (strings).
• Exclude the queried person from the returned network.
• Return distinct identifiers; the graph may contain cycles, so guard against revisiting nodes.
• If the person never appears, return an empty list.

Hints

1. Build an undirected adjacency list (each edge added in both directions), then explore the connected component with BFS or DFS.
2. Track visited nodes so cycles do not cause infinite loops or duplicate entries.
3. Remove the starting person from the result before returning, and sort for a deterministic answer.

Transaction Network — Part 3: Find Network Within N Degrees

Extend findNetwork to accept a degree limit n. Given the undirected transaction graph (list of [x, y] pairs), a person, and an integer n, return all customers within at most n degrees of separation from person, excluding person.

• Degree 1 = direct transaction partners
• Degree 2 = partners of partners
• ... up to degree n

Because the graph may contain cycles, each customer should be counted at its shortest degree of separation, and only included if that shortest distance is <= n. Return the result as a sorted list of distinct identifiers. If person is absent or n <= 0, return an empty list.

Example 1 Transactions: (a,b), (b,c), (a,d), (d,e), (g,f)

• findNetwork(a, 1) -> ['b', 'd']
• findNetwork(g, 1) -> ['f']

Example 2 (cycle) Transactions: (a,b), (b,d), (d,c), (c,a)

• findNetwork(a, 1) -> ['b', 'c']

Example 3 Transactions: (a,b), (b,c), (c,d), (b,e), (c,f), (d,g), (f,g), (g,h)

• findNetwork(d, 2) -> ['b', 'c', 'f', 'g', 'h']
• findNetwork(h, 3) -> ['c', 'd', 'f', 'g']
• findNetwork(a, 1) -> ['b']

Constraints

• 0 <= number of transactions
• Each transaction is an undirected pair of customer identifiers (strings).
• n is an integer; if n <= 0 the result is empty.
• Exclude the queried person.
• Count each customer at its shortest degree of separation; the graph may contain cycles, so use a level-order (BFS) traversal and mark nodes visited the first time they are reached.

Hints

1. Level-order BFS naturally tracks degrees of separation: the level at which you first reach a node is its shortest distance from the source.
2. Carry a depth with each queued node; stop expanding once depth reaches n so you never include nodes beyond n degrees.
3. Mark a node visited the first (shortest) time you reach it, which both prevents cycle re-entry and guarantees each node is counted at its minimum degree.