1.用map定义哈希表,达到o(n)
2.st[i][j]表示i是否联系过j,实现确认相互联系
3.suspect数组存储所有嫌疑人
4.两者之间可能通过间接关系有联系的,使用”并查集”(简洁)
#include<bits/stdc++.h>
using namespace std;
const int N=1100;
map<int,int> e[N];
bool st[N][N];
vector<int> suspect;
int fa[N],k,n,m;
int find(int x)
{
if(fa[x]!=x)fa[x]=find(fa[x]);
return fa[x];
}
int main()
{
cin>>k>>n>>m;
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
e[a][b]+=c; //哈希表存储a人跟b人通话的总时间
st[a][b]=true;
}
//o(n)
for(int i=1;i<=n;i++)
{
double cnt1=0,cnt2=0;
for(auto t:e[i])
{
if(t.second<=5)
{
cnt1++; //短通话的个数
if(st[t.first][i])cnt2++; //有回电的个数
}
}
if(cnt1>k&&cnt2/cnt1<=0.2)
{
suspect.push_back(i); //此时已经是有序的无重复的
fa[i]=i;
}
}
if(suspect.empty())puts("None");
else
{
int c=0,l=suspect.size();
for(int i=0;i<l;i++)
{
for(int j=i+1;j<l;j++)
{
int x=suspect[i],y=suspect[j];
if(st[x][y]&&st[y][x]) //相互联系过
{
int q=find(x),p=find(y);
if(q>p)swap(q,p);
fa[p]=q; //大->小 //保证输出是合法的
}
}
}
for(int i=1;i<=n;++i)
{
bool flag=0;
for(int j=1;j<=n;j++)
{
if(find(j)==i) //不是嫌疑人的自动跳过,因为不存在0的根节点 //不是每个点都经过了路径压缩,所以用find函数
{
cout<<j<<' ';
flag=1;
}
}
if(flag)puts(""); //保证输出格式正确
}
}
return 0;
}