#D. 【基础】团队数量
【基础】团队数量
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
说明
芝加哥组织了一场激烈的军事竞赛,很多国家的军人慕名而来,他们要么是队友,要么是敌人。
现建立如下规则:
我的队友的队友,是我的队友;
我的敌人的敌人也是我的队友;
两个人只要是队友,就认为他们属于同一团队,现给你若干参赛军人之间的关系,请问:最多有多少个团队?
输入格式
第一行是一个整数N(2<=N<=1000),表示参赛的人数(从1编号到N)。 第二行M(1<=M<=5000),表示关于参赛者的关系信息的条数。 以下M行,每行可能是F p q或是E p q(1<=p q<=N),F表示p和q是队友,E表示p和q是敌人。输入数据保证不会产生信息的矛盾。
输出格式
输出文件只有一行,表示最大可能的团队数。
样例
6
4
E 1 4
F 3 5
F 4 6
E 1 2
3
提示
样例结束:[3,5]是一个团队,[4,6]是一个团队,由于1和4、1和2都是敌人,2和4自然成为队友,因此[2,4,6]成为团队,1单独为1个团队,最终有3个团队。
第七届SWPU-ACM老生预选赛
- Status
- Done
- Rule
- ACM/ICPC
- Problem
- 187
- Start at
- 2022-9-19 14:00
- End at
- 2022-10-28 14:00
- Duration
- 936 hour(s)
- Host
- Partic.
- 45