图论+并查集问题
坑点如下
1,利用line数组来依次判断可怀疑对象,将嫌疑人依次放入temp数组。
2,在temp数组中用DFS方法,将所有存在相互通话的嫌疑人合并。
3,DFS过程中temp1的顺序被打乱,需要重新排序。
3,vector<vector>ans中sort函数的用法,如图,按照第一个元素大小排列,如相同,则按照下一个元素大小排列,直到排列完成。
3 4
3 4 5
4
整体代码如下
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<unordered_map>
#include<iostream>
#include<set>
using namespace std;
vector<int>temp,temp1;
vector<vector<int>>ans;
int k,n,m;
int line[1010][1010];
int in[1010],out[1011],vis[1010];
void DFS(int s){
vis[s]=1;
temp1.push_back(s);
for(int &r:temp){
if(vis[r]==0&&line[s][r]&&line[r][s])DFS(r);
}
}
int main(){
cin>>k>>n>>m;
int c,re,dur;
for(int i=0;i<m;i++){
cin>>c>>re>>dur;
line[c][re]+=dur;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(line[i][j]>0&&line[i][j]<=5)
{ out[i]++;
if(line[j][i]>0)
in[i]++;
}
}
}
for(int i=1;i<=n;i++){
if(out[i]>k&&in[i]*5<=out[i])
temp.push_back(i);
}
for(int &r:temp){
if(!vis[r]){
temp1.clear();
DFS(r);
sort(temp1.begin(),temp1.end());
if(!temp1.empty())ans.push_back(temp1);
}
}
sort(ans.begin(),ans.end());
if(ans.size()==0)printf("None\n");
else{
for(int i=0;i<ans.size();i++)
{ for(int j=0;j<ans[i].size();j++)
{ printf("%d",ans[i][j]);
if(j!=ans[i].size()-1)printf(" ");}
printf("\n");}
}
return 0;
}