#D. 【基础】团队数量

    Type: Default 1000ms 128MiB

【基础】团队数量

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老生预选赛

Not Attended
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