Below is a question based on CLRS, about using an algorithm to reach a balance between a group of friends. I figured the best way to do this, is through the use of a DFS algorithm. Below the question is some psuedocode I wrote using the formal algorithm of a DFS search. My question is, how do I get the algorithm to balance out the debt between every student?
The input for your algorithm consists of two lists $owing$ and $friendship$. The length of the list $owing$ is the total number of students; $owing[i]$ is the amount that student $i$ is owing $(0 \leq i \leq len(owing)-1)$, and it is an integer than can be positive (owing money), negative (owed money) or zero. The list $friendship$ is a list of pairs that represent the remaining friendships, i.e., a pair $(i, j)$ means student $i$ and student $j$ are still friends and can still talk and give money to each other. Devise an efficient algorithm which, given the two input lists, returns whether or not it is possible for everyone to get even.
The algorithm uses three colors (white/grey/black) to measure not visited/visited/cleared. What I want to happen is, it goes through a single cluster of friends, then checks to see if the balance of that friends group is equal to 0 (everyone can pay each other back). If not, returns failure. The issue is, let's say it does pass through that circle of friends- what if needs to go to another friends group? How will it balance out when that friends group might have a different adjacency list. Any advice on how to make sure everyone can pay each other and return 0?
Owing = false Owed = false pathTotal = 0 DFS(owing, friendship): for student in owing: student.color = white student.pred = null student.area = null for student in friendship: if student.color == white: DFS_VISIT(student, owing, friendship) DFS_VISIT(student, owing, friendship) // Get all students current student is friends with for x in friendship: if x pair student: student.adj = student.adj + x // Check if adjacent members have not been visited for i in student.adj: if i.color != white: if owing[i] > 0: Owing = true else if owing[i] < 0: Owed = true // If it hasn't been visited if student.color == white: Owing = false Owed = false if student.pred == null: if owing[student] != 0: return "Failure" else: pathTotal = pathTotal + owing[student] // Calculated debt student.color = grey // Recursively go through the rest of the list for t in student.adj: if t.colot == white: t.pred = student DFS_VISIT(t, owing, friendship) // All neighbors visited student.color = black;