题目描述
“每行输出一个犯罪团伙的所有嫌疑人信息,按编号升序顺序输出团伙内的所有嫌疑人编号。
团伙之间,按其第一名成员编号的升序顺序排序。”
第一名成员编号:较小的编号————*让较小的成为祖宗*
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
满分答案
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
//诈骗团伙
using namespace std;
const int maxn=1005;
int k,n,m;
int father[maxn],g[maxn][maxn],visit[maxn];
vector<int> gang;
int findfather(int v){
return father[v]==v?v:(father[v]=findfather(father[v]));
}
void u(int a,int b){
int faa=findfather(a);
int fab=findfather(b);
if(faa<fab) father[faa]=fab;
else if(fab<faa) father[fab]=faa;
}
int main(){
scanf("%d %d%d",&k,&n,&m);
fill(g[0],g[0]+maxn*maxn,0);
fill(visit,visit+maxn,0);
for(int i=1;i<=n;i++) father[i]=i;
int a,b,c;
for(int i=0;i<m;i++){
scanf("%d %d%d",&a,&b,&c);
g[a][b]+=c;//有向
}
for(int i=1;i<=n;i++){
int shortc=0,backc=0;
for(int j=1;j<=n;j++){
if(j==i) continue;
if(g[i][j]>0&&g[i][j]<=5){//<5min
shortc++;
if(g[j][i]>0) backc++;
}
}//编号为i的人
if(shortc>k&&backc*5<=shortc) gang.push_back(i);
}
for(int i=0;i<gang.size();i++){
for(int j=0;j<gang.size();j++){
if(j==i) continue;
int x=gang[i];int y=gang[j];
if(g[x][y]&&g[y][x])//两个嫌疑人有联络,
u(x,y);//一个团伙,合并 编号大的当爸爸
}//这里只是合并,下面比较父节点时路径压缩
}
for(int i=0;i<gang.size();i++){
int x=gang[i];
if(visit[x]==1) continue;
visit[x]=1;printf("%d",x);//输出嫌疑人,再找跟他一个团伙的
for(int j=i+1;j<gang.size();j++){
int y=gang[j];
if(visit[y]==0&&findfather(x)==findfather(y)){
visit[y]=1;printf(" %d",y);
}
}
printf("\n");
}
if(gang.size()==0)printf("None\n");
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <vector>
#include <unordered_map>
#include <map>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn = 1002;
int K, N, M;
unordered_map<int, int> G[maxn]; // 邻接表
int G2[maxn][maxn]; // 哈希表,G2[a][b] == 1表示a给b打过电话
unordered_map<int, int> father; // 并查集
map<int, vector<int>> ans; // 存储输出结果,key为团伙头目(最小序号者),value为所有同伙(包括自己)
int findFather (int index) {
int x = index;
while (x != father[x]) {
x = father[x];
}
return x;
}
void Union (int a, int b) {
int fa = findFather(a);
int fb = findFather(b);
if (fa == fb) return;
// 保证序号小的成为头
if (fa < fb) father[fb] = fa;
else father[fa] = fb;
}
void test () {
int i, t1, t2, t3;
scanf("%d %d %d", &K, &N, &M);
for (i = 0; i < M; i++) {
scanf("%d %d %d", &t1, &t2, &t3);
G[t1][t2] += t3;
G2[t1][t2] = 1;
}
for (i = 1; i <= N; i++) {
// count1是给不同人short phone的数量,count2是接到short phone中回拨的人数
int count1 = 0, count2 = 0;
// 简单优化:如果i的拨打人数小于等于阈值,i一定不是可疑分子
if (G[i].size() <= K) continue;
for (auto& item : G[i]) {
if (item.second <= 5) {
count1++;
if (G2[item.first][i]) {
count2++;
}
}
}
// 挑出可疑分子,初始化并查集
if (count1 > K && count2 * 5 <= count1) {
father[i] = i;
}
}
if (father.empty()) {
printf("None");
return;
}
// 双重循环,可疑分子两两合并
for (auto it1 = father.begin(); it1 != father.end(); it1++) {
auto it2 = it1;
int a = it1->first;
for (it2++; it2 != father.end(); it2++) {
int b = it2->first;
if (G2[a][b] && G2[b][a]) {
Union(a, b);
}
}
}
// 整理各团伙成员及头目,头目作为key,让map自动排序
for (auto &item : father) {
ans[findFather(item.first)].push_back(item.first);
}
for (auto &item : ans) {
vector<int> &temp = item.second;
sort(temp.begin(), temp.end());
for (i = 0; i < temp.size(); i++) {
printf("%d%c", temp[i], i < temp.size() - 1 ? ' ' : '\n');
}
}
}
int main () {
test ();
return 0;
}