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

柔情只为你懂 2021-11-26 14:20 249阅读 0赞

## 并查集适用问题举例 ##

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

### 更详细请查看 ###

[http://www.omegaxyz.com/2019/02/25/union-find/][http_www.omegaxyz.com_2019_02_25_union-find]

## 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 K 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. A makes a short phone call to B means that the total duration of the calls from A to B 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 K (≤500, the threshold（阈值） of the amount of short phone calls), N (≤103, the number of different phone numbers), and M (≤105, the number of phone call records). Then M lines of one day’s records are given, each in the format:

**caller receiver duration**

where caller and receiver are numbered from 1 to N, 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 Input 1: ####

5 15 31  
1 4 2  
1 5 2  
1 5 4  
1 7 5  
1 8 3  
1 9 1  
1 6 5  
1 15 2  
1 15 5  
3 2 2  
3 5 15  
3 13 1  
3 12 1  
3 14 1  
3 10 2  
3 11 5  
5 2 1  
5 3 10  
5 1 1  
5 7 2  
5 6 1  
5 13 4  
5 15 1  
11 10 5  
12 14 1  
6 1 1  
6 9 2  
6 10 5  
6 11 2  
6 12 1  
6 13 1

#### Sample Output 1: ####

3 5  
6

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.

#### Sample Input 2: ####

5 7 8  
1 2 1  
1 3 1  
1 4 1  
1 5 1  
1 6 1  
1 7 1  
2 1 1  
3 1 1

#### Sample Output 2: ####

None

#### C++代码： ####

#include<iostream>
    #include<vector>
    #include<algorithm>
    #include<cstdio>
    #include<map>
     
    using namespace std;
     
    int durcnt[1010][1010]; //统计总通话时间
    int father[1010]; //并查集father
     
    int findFather(int n){
        
        int a = n;
        while(a != father[a])a = father[a];
        while(n != father[n]){
        
            int z = n;
            n = father[n];
            father[z] = a;
        }
        return a;
    }
     
    void setUnion(int x, int y){
        
        int fx = findFather(x);
        int fy = findFather(y);
        if(fx != fy){
        
            if(fy < fx) swap(fx, fy); //序号较小的作为leader
            father[fy] = fx;
        }
    }
     
    void init(int n){
        
        for(int i = 1; i <= n; i++)father[i] = i;
    }
     
    int main(){
        
        map<int, vector<int> > gangs;
        vector<int> suspects;
        int K, N, M;
        cin>>K>>N>>M;
        init(N);
        int c, r, d;
        for(int i = 0; i < M; i++){
        
            cin>>c>>r>>d;
            durcnt[c][r] += d;
        }
     
        //判断是否是诈骗团伙
        for(int i = 1; i <= N; i++){
        
            int sumDiff = 0, rcall = 0;
            for(int j = 1; j <= N; j++){
        
                if(durcnt[i][j] > 0 && durcnt[i][j] <= 5){
        
                    sumDiff++;
                    if(durcnt[j][i] > 0)rcall++;
                }
            }
            if(sumDiff > K && 1.0 * rcall / sumDiff <= 0.2)suspects.push_back(i);
        }
        
        //找出每一个团伙的成员
        for(int i = 0; i < suspects.size(); i++){
        
            for(int j = i; j < suspects.size(); j++){
        
                if(durcnt[suspects[i]][suspects[j]] > 0 && durcnt[suspects[j]][suspects[i]] > 0){
        
                    setUnion(suspects[i], suspects[j]); //同一个团伙的合并
                }
            }
        }
        for(int i = 0; i < suspects.size(); i++){
        
            int leader = findFather(suspects[i]);
            gangs[leader].push_back(suspects[i]);
        }
        if(gangs.size() == 0)cout<<"None"<<endl;
        else{
        
            for(int i = 0; i < gangs.size(); i++){
        
                sort(gangs[i].begin(), gangs[i].end());
                for(int j = 0; j < gangs[i].size(); j++){
        
                    printf("%d%s", gangs[i][j], j == gangs[i].size() - 1 ? "\n" : " ");
                }
            }
        }
        return 0;
    }

[http_www.omegaxyz.com_2019_02_25_union-find]: http://www.omegaxyz.com/2019/02/25/union-find/
[omegaxyz.com]: http://omegaxyz.com