Choosing Chicken-Fight Teams
Time limit2sMemory limit256 MB
Given friend/enemy relations among students where friends of friends are friends and enemies of enemies are friends, find the maximum number of valid teams.
- Level
Medium6 of 10
- Topics
- Union-find, Graph
- Solved
- No attempts yet
Problem
Chicken fighting is a long-standing tradition in this fictional world. At this camp, a chicken-fighting tournament is being held again. To run the tournament, every student must know who is on the same side and who is not.
Teams are determined from the students' relationships by these rules:
- A friend of my friend is also my friend.
- An enemy of my enemy is also my friend.
If two students are friends, they must belong to the same team. Also, everyone in the same team must be friends with each other.
Given the known relationships among the students, write a program that finds the maximum possible number of teams that can be formed.
Input
The first line contains the number of students n. The students are numbered from 1 to n. (2 <= n <= 1000)
The second line contains the number m of known relationships between students. (1 <= m <= 5000)
Each of the next m lines contains one relationship in the form F p q or E p q, separated by spaces. (1 <= p < q <= n)
If the first letter is F, students p and q are friends. If it is E, they are enemies.
The input is guaranteed to have no contradiction. In other words, no two students are both friends and enemies at the same time.
Output
Print the maximum possible number of teams on the first line.
Hint
One optimal grouping is to place student 1 alone, students 2, 4, and 6 together, and students 3 and 5 together. This gives the maximum number of teams.