问题1027--垃圾邮件过滤器

1027: 垃圾邮件过滤器

时间限制: 2 Sec  内存限制: 128 MB
提交: 207  解决: 52
[提交] [状态] [讨论版] [命题人:]

题目描述

要处理垃圾邮件,就要对邮件归类。现在有n封邮件,邮件编号0~n-1,m个操作:
1.     M X Y表示邮件X和Y是同一类
2.     S X  表示邮件X是特殊类,这个时候,他就要独立出来单独归类
比如有3封邮件,3个操作:M 0 1,M 1 2,S 1
前两个操作表示0 1 2封邮件都属于一类,经过第三个操作后,发现1是特殊类,但0 2还是属于同一类,于是总共有两类邮件。
现在问题就是给你这些邮件和操作,问总共有几类邮件?

输入

输入n m
输入m个操作,如描述格式

输出

输出有几类邮件

样例输入 Copy

3 3
M 0 1
M 1 2
S 1

样例输出 Copy

2

提示

【样例说明】
其他样例:
输入:
5 6
M 0 1
M 1 2
M 1 3
S 1
M 1 2
S 3
输出:
3
解释:
前三个操作把0 1 2 3归为一类,
然后发现1要单独归类,于是把1与0 2 3分开
后来发现1和2是同一类,于是继续把1归到2的分类中
最后发现3是单独一类
最终0 1 2是一类,3一类,4一类
总共3类
【数据规模和约定】
1<=N<=10^5
1<=M<=10^6

来源/分类