graph search algorithm - DFS
In this problem you have to find that if you start DFS from a node how many nodes are under this node in the DFS-tree and choose the maximum value of these for output.
Cause the input size is small and you are facing a DAG, don't think of complex algorithms to solve this problem, easily run DFS for each node and count how many nodes are invoked from this DFS and don't worry about cycles(there are no cycles in this problem). O(n^3)
data structures:
mat[101][101] = adjacency matrix
mark[101] = to mark which nodes are visited
Subscribe to:
Post Comments (Atom)
-
Link to the problem on Timus Online Judge First of all there are two kinds of input which the answer is zero, first if sum % 2 == 1 or se... -
Link to the problem on Timus Online Judge The problem statement is completely straight forward with no hidden tricks :). Yeah yeah I know...
-
Link to the problem on Timus Online Judge This is a Computational Geometry problem. No 3 points lie on the same line and this is a great...
No comments:
Post a Comment