并查集适用问题举例
- 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.
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:
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
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:
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.
|
|
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:
C++代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
#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; } |
