并查集适用问题举例
1、已知，有n个人和m对好友关系
2、如果两个人是直接的或者间接的好友（好友的好友的好友。。。），那么他们属于一个集合，就是一个朋友圈中
3、写出程序，求这n个人中一共有多少个朋友圈
更详细请查看
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];
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);
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;
}
更多内容访问 omegaxyz.com
网站所有代码采用Apache 2.0授权
网站文章采用知识共享许可协议BY-NC-SA4.0授权
© 2019 • OmegaXYZ-版权所有 转载请注明出处
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
