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

并查集适用问题举例

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

更详细请查看

并查集简介与实例C++实现

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$ ( $\leq 500$ , the threshold（阈值） of the amount of short phone calls), $N$ ( $\leq 1 0^{ 3 }$ , the number of different phone numbers), and $M$ ( $\leq 1 0^{ 5 }$ , the number of phone call records). Then $M$ lines of one day's records are given, each in the format:

caller receiver duration

1 2	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

3 5

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

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;
}

#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;

}

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

并查集适用问题举例

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

Input Specification:

Output Specification:

Sample Input 1:

Sample Output 1:

Sample Input 2:

Sample Output 2:

C++代码：

大模型AlpacaFarm分析

NLG文本评估任务或许并不需要真值或参考文本

大模型中的RepE表征工程

大模型也是一种优化器（LLM as Optimizer）

全栈开发与快速部署Demo

学术idea自动发现与生成

自回归语言模型（language model）Python实现

粉丝期待的三体电影宇宙（近四十部电影与电视剧集）

基于历史对比学习的时序知识图谱推理

泰拉瑞亚Terriaria快速部署Linux服务器

留下评论取消回复

并查集适用问题举例

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

Input Specification:

Output Specification:

Sample Input 1:

Sample Output 1:

Sample Input 2:

Sample Output 2:

C++代码：

相关文章

留下评论取消回复