Sunday, October 17, 2010

599 - The Forrest for the Trees - UVA

graph search algorithm - DFS

In this problem you have to find the number of components in a graph and you have to distinguish which components are isolated vertices. Easily run DFS for each unvisited node and count the number of components, set a counter before running DFS to find the number of vertices in a component, increment it at the beginnig and if this number was 1, it is an isolated vertex.

No comments:

Post a Comment

USACO - Prime Palindromes

I just skimmed the problem statement and panicked of the high boundary of the input, but something inside told me don't worry everyth...