PROBLEM LINK:
DIFFICULTY:
EASY
PREREQUISITES:
Graph, Strongly Connected Components
PROBLEM:
Given a team consisting of n players and m ropes are used to tie them. Captain of the team finds the player connected to a single player only, and throws him out. He repeats this process till all such players are removed. Determine how many players will be there at the end of the process.
EXPLANATION:
The problem statement describes a graph where the cricket players represent vertices and the ropes represent edges between the nodes. Then we just need to keep iterating over all the vertices in the graph to find a group of vertices all having only a single neighbour and remove them from the graph. The number of such group of vertices is the final answer.
SOLUTIONS:
Author’s solution can be found here.