Problem Link - Cricket Match
Problem Statement -
There are N people numbered from 1 to N and they want to play a cricket match between them by forming two teams that may not be of the same size. There are M pairs of peoples and for each pair of peoples, they can not be in the same team. Now Chef wants to know if there is any way to split them into two teams such that Chef can organize the cricket match between two teams. If possible then print "YES" (without quotes), otherwise print "NO" (without quotes).
Approach -
The problem can be visualized as graph where each person is a node, and each restricted pair forms an edge. The task is to split the nodes into two groups, which requires checking if the graph is bipartite. In a bipartite graph, nodes can be divided into two sets where no two nodes within the same set are adjacent. To verify this, we can use DFS (or BFS), assigning each node a level or “depth” during traversal. We start with an unvisited node, assigning it an initial level (0), and assign alternating levels (0 and 1) to adjacent nodes.
If we find two adjacent nodes with the same level, the graph contains an odd-length cycle, meaning it’s non-bipartite, so we output "NO". This indicates we can’t separate the nodes into two groups. If no such condition occurs in any graph component, we output "YES".
Time Complexity
O(N + M), where N is the number of nodes and M is the number of edges.
Space Complexity
O(N + M), for storing the graph and levels of nodes.