亲戚时间限制: 1000 ms 内存限制: 65536 KB 提交数: 374 通过数: 127 【题目描述】若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的某个人所在家族的人数。 规定:x和y是亲戚,y和z是亲戚,那么x和z也是亲戚。如果x,y是亲戚,那么x的亲戚都是y的亲戚,y的亲戚也都是x的亲戚。 【输入】第一行:三个整数n,(n≤100,000,m≤200,000),分别表示有n个人,m个信息。 以下m行:信息包含两种形式: M a b:表示a和b具有亲戚关系。 Q a:要求输出a所在家族的人数。 【输出】要求输出a所在家族的人数。 【输入样例】5 10 M 3 2 Q 4 M 1 2 Q 4 M 3 2 Q 1 M 3 1 Q 5 M 4 2 Q 4 【输出样例】1 1 3 1 4 【代码分析】 |
详细解决方案
并查集 信息奥赛一本通 亲戚
热度:83 发布时间:2024-01-15 08:20:26.0
相关解决方案