# 并查集应用——PAT甲级2019春季

## 并查集适用问题举例

• 1、已知，有n个人和m对好友关系
• 2、如果两个人是直接的或者间接的好友（好友的好友的好友。。。），那么他们属于一个集合，就是一个朋友圈中
• 3、写出程序，求这n个人中一共有多少个朋友圈

## PAT-2019年春季考试-甲级-3

Telefraud（电信诈骗） remains a common and persistent problem in our society. In some cases, unsuspecting victims lose their entire life savings. To stop this crime, you are supposed to write a program to detect those suspects from a huge amount of phone call records.

A person must be detected as a suspect if he/she makes more than  short phone calls to different people everyday, but no more than 20% of these people would call back. And more, if two suspects are calling each other, we say they might belong to the same gang.  makes a short phone call to  means that the total duration of the calls from  to  is no more than 5 minutes.

### Input Specification:

Each input file contains one test case. For each case, the first line gives 3 positive integers  (, the threshold（阈值） of the amount of short phone calls),  (, the number of different phone numbers), and  (, the number of phone call records). Then  lines of one day’s records are given, each in the format:

where caller and receiver are numbered from 1 to , and duration is no more than 1440 minutes in a day.

### Output Specification:

Print in each line all the detected suspects in a gang, in ascending order of their numbers. The gangs are printed in ascending order of their first members. The numbers in a line must be separated by exactly 1 space, and there must be no extra space at the beginning or the end of the line.

If no one is detected, output None instead.

### Sample Output 1:

Note: In sample 1, although 1 had 9 records, but there were 7 distinct receivers, among which 5 and 15 both had conversations lasted more than 5 minutes in total. Hence 1 had made 5 short phone calls and didn’t exceed the threshold 5, and therefore is not a suspect.