Ice Battle II: Minimum Record Deletions for Bipartite Teams

ID: 13804

Type: Default

1000ms

256MiB

The popular online game Ice Battle is now being extended to a team mode in Ice Battle II. In this new mode, players are divided into two teams, Team I and Team Sing, according to their one‐on‐one match records from Ice Battle.

The rule is: if two players have ever faced each other in a one‐on‐one match, they must be on different teams. Every team must have at least one member, although the sizes of the two teams may differ.

However, certain match records may make it impossible to form two teams. For example, if three players have all played against each other, they would all have to be in different teams! In order to resolve such conflicts, the game server is allowed to delete some of the records. The goal is to delete the minimum number K of records such that the remaining match records permit the players to be divided into two teams. In addition, if K is three or more, the game will be postponed (and you should output 0 in that case).

For instance:

In one scenario, deleting just one record (for example, the match between player A and B) is enough to allow a valid division into two teams.
In another scenario, there are three different ways to delete exactly one record (e.g. {A-B}, {A-C}, or {B-C}) to make the division possible; thus, the answer would be 3.
Similarly, in a different record set, the minimum required deletions might be 2, and there could be 3 different pairs of records whose removal would work.

Your task is to implement the function

$$\texttt{long long count_ways(int N, vector U, vector V);} $$

Here, N is the number of players, and U and V are vectors of equal size M representing that there is a match record between player U_i and player V_i (players are numbered from 1 to N). The function should return the number of different ways to delete exactly K records (where K is the minimum number needed) so that the remaining records allow the players to be divided into two teams. If the match records already permit a valid division (i.e. no record needs to be deleted), return 1. If it is impossible to achieve a valid division with at most 2 deletions, return 0.

Note: The order in which records are deleted does not matter. You may create additional helper functions if necessary. The submitted code should not perform any input/output operations or access external files.

inputFormat

The input consists of multiple lines. The first line contains two integers N and M, the number of players and the number of match records, respectively. Then follow M lines, each containing two integers, indicating a match record between two players. It is guaranteed that players are numbered from 1 to N.

outputFormat

Output a single integer representing the number of ways to delete the minimum number of match records such that the remaining records allow a division into two teams. If no deletion is needed, output 1; if it is impossible with at most 2 deletions, output 0.

sample

3 2
1 2
2 3

</p>

#P11712. Ice Battle II: Minimum Record Deletions for Bipartite Teams

Ice Battle II: Minimum Record Deletions for Bipartite Teams