Lynbrook Computer Science

In today’s meeting, we went over last week’s PotW solution and  a couple searching algorithms. We focused mainly on depth-first search(DFS) and breadth-first search(BFS). Regarding these search algorithms and graph theory, more information and pseudocode can be found in our meeting slides. The new PotW is:

• This problem has nothing to do with cows, but for some reason cows are nodes, and friendships are edges. Check if the graph is a tree.
• Each edge is undirected, since friendships are mutual (hopefully)
• A tree is a graph such that all nodes are connected and there is only one unique way to get between each two nodes
• The first line of the input contains the number of nodes (less than 1,000,000) and then the number of edges (also less than 1,000,000)
• Each successive line contains an edge, and has two indices, where indices are numbered starting from one
• The output should be either “YES” or “NO”
• Sample Input:
  3 2
  1 2
  2 3
• Sample Output:
  YES

The entire problem is worth 30 points.