- ID : UVA - 10305 - Ordering Tasks
- Language : Java , C++
- Status : Accepted - Accepted
- Type : Topological Sort.
- Time : 6 Hours.
- Solution :
- Source Removal Method or DFS
- Calculate in Degree.
- Use a queue and insert at first all edges with 0 in Degree those who must be finished first.
- Dequeue every time a node and decrease the in-degree of all it's neighbours as this node is considered to be removed from the queue or the task is done
- each time you decrease the degree of the node. check if this task is available now ( i.e it's degree is zero that means that all of it's dependencies is already finished.
- Problems :
- Check for special cases in the input. the m could be a zero and that what stopped me for 6 hours and I don't know what's wrong with my solution. I discovered that I have to remove the m!=0 condition from the while loop statement.
- I wasn't able to submit the DFS solution don't know what's the reason. but I decided to solve more problems for this period and come to this later
- Code :
Algorithms Problems Archive
This Blog is a Personal record for All The Algorithms Problems I've Solved. It shouldn't be taken as a reference for optimal solutions because I'm just a beginner.
Friday, March 4, 2011
UVA - 10305 - Ordering Tasks
Subscribe to:
Posts (Atom)