Problem Link - Among Us
Problem Statement
Earth has been invaded by man-eating parasites that are indistinguishable from humans. In a desperate attempt to prevent human extinction, N ambitious astronauts venture into outer space, to get away from the parasites. The only problem is that there may already be some among them!
The astronauts are numbered 1 to N. You receive Q statements in total from the astronauts, possibly more than one statement from the same astronaut, possibly none at all from some astronauts. Each statement is one of the following two types:
- 1 i j, meaning that astronaut i accuses astronaut j of being a parasite. In other words, j must be a parasite according to i.
- 2 i j, meaning that astronaut i vouches for astronaut j. In other words, j must be human according to i.
It is a known fact that no human will ever tell a lie, and no parasite will ever tell the truth. Refer to the sample explanation below for further clarification.
You do not know which of the astronauts are parasites. It is possible that they all are. It is also possible that none of them are.
The statements made by the astronauts are said to be consistent if each astronaut can be labelled as either a human or a parasite such that all parasites lie, while all humans tell the truth.
Your task is to determine whether the statements made by the astronauts are consistent. If they are consistent report the maximum possible number of parasites.
Approach
The problem can be solved by treating the astronauts as nodes in a graph, with statements forming two types of edges: one representing accusations ( type 1) and the other representing support ( type 2). For accusations, i and j belong to opposite groups, while for support, i and j belong to the same group. We perform a breadth-first search (BFS) to label each astronaut as either human or parasite. During BFS, if an accusation edge is encountered, we mark the other astronaut as the opposite type, and if a support edge is encountered, we mark them as the same type. If a conflict arises where an astronaut cannot be assigned consistently, we conclude the statements are inconsistent. Otherwise, the maximum possible number of parasites is calculated by choosing the larger group in each connected component.
Time Complexity
The time complexity is O(N + Q), where N is the number of astronauts and Q is the number of statements.
Space Complexity
The space complexity is O(N + Q) to store the graph and track visited astronauts.