1
$\begingroup$

I'm trying to use the concept of DFS traversal to go through a cycle, and attempt to get a balance of 0 in the end. Each student either owes or is owed some money, so I'm trying to go through all of said students and make sure each one can pay the other.

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.


I've attempted to write psuecode for it, and it runs in O(|V + E|), the normal runtime of a DFS. I was wondering if it's correct, and whether there's a way to have it run more efficiently?

The general logic behind it is, visited all members in the owing list but paying the debts through friendship. Check that the total sum all frienships in this path can total up to 0. If it doesn't returns failure.

$\endgroup$

closed as unclear what you're asking by Yuval Filmus, Evil, David Richerby, Juho, Rick Decker Mar 30 '17 at 18:11

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Mar 22 '17 at 21:04
  • $\begingroup$ If you want to know whether your algorithm is correct, try running it on small hand-written test cases, run it on a million randomly generated test cases, then try to write a proof of correctness (and simultaneously, search for a test case where it gives the wrong answer). $\endgroup$ – D.W. Mar 22 '17 at 21:05
  • $\begingroup$ @D.W. I made some modifications to the post, is it okay now or should I change it further? $\endgroup$ – Andrew Raleigh Mar 22 '17 at 22:07
  • 2
    $\begingroup$ I don't see how deleting the pseudocode improves the question. Without your pseudocode, we cannot tell whether your pseudocode is correct. $\endgroup$ – Yuval Filmus Mar 25 '17 at 22:40
  • $\begingroup$ cs.stackexchange.com/q/72049/755 $\endgroup$ – D.W. Mar 26 '17 at 22:35

Browse other questions tagged or ask your own question.