A70721. 团队数量
编程题
基础
知识点
题目描述
芝加哥组织了一场激烈的军事竞赛,很多国家的军人慕名而来,他们要么是队友,要么是敌人。
现建立如下规则:
我的队友的队友,是我的队友;
我的敌人的敌人也是我的队友;
两个人只要是队友,就认为他们属于同一团队,现给你若干参赛军人之间的关系,请问:最多有多少个团队?
输入格式
第一行是一个整数 N (2 \le N \le 1000),表示参赛的人数(从 1 编号到 N )。
第二行 M (1 \le M \le 5000),表示关于参赛者的关系信息的条数。
以下 M 行,每行可能是 F p q 或是 E p q(1 \le p,q \le N),F 表示 p 和 q 是队友,E 表示 p 和 q 是敌人。
输入数据保证不会产生信息的矛盾。
输出格式
输出文件只有一行,表示最大可能的团队数。
输入输出样例
输入 #1
6 4 E 1 4 F 3 5 F 4 6 E 1 2
输出 #1
3
说明/提示
## 思路
用并查集维护连通:find 找根,unite 合并集合。
## 步骤
1. 初始化每个元素的父节点为自己。
2. 按操作合并或查询是否同根。
3. 输出题面要求的连通信息。
用并查集维护连通:find 找根,unite 合并集合。
## 步骤
1. 初始化每个元素的父节点为自己。
2. 按操作合并或查询是否同根。
3. 输出题面要求的连通信息。