并查集代码:
//重要的是映射
#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_map>
using namespace std;
const int N=1010,M=2*N;
int p[M],w[M];
unordered_map<string,int>h1;
unordered_map<int,string>h2;//映射
int n,k;
int idx;
int cnt[M];
int find(int i){
if(i!=p[i]){
p[i]=find(p[i]);
}
return p[i];
}
int sum[M];
int st[M];
int main(){
cin>>n>>k;
for(int i=0;i<M;i++){
p[i]=i;
sum[i]=1;
}
while(n--){
string a,b;
int c;
cin>>a>>b>>c;
if(!h1.count(a))
h1[a]=++idx;
if(!h1.count(b))
h1[b]=++idx;
h2[h1[a]]=a;
h2[h1[b]]=b;
int ai,bi;
ai=find(h1[a]);
bi=find(h1[b]);
if(ai!=bi){
sum[ai]+=sum[bi];
p[bi]=ai;
}
cnt[h1[a]]+=c;
cnt[h1[b]]+=c;
}
vector<string>res;
for(int i=1;i<=idx;i++){
int temp=find(i);
int id=i;
int ssum=0;
if(!st[temp]){
for(int j=1;j<=idx;j++){
if(find(j)==temp){
ssum+=cnt[j];
if(cnt[j]>cnt[id]){
id=j;
}
}
}
ssum/=2;
if(ssum>k&&sum[temp]>=3){
res.push_back(h2[id]);
}
st[temp]=1;
}
}
cout<<res.size()<<endl;
sort(res.begin(),res.end());
for(auto &t:res){
cout<<t<<' '<<sum[find(h1[t])]<<endl;
}
return 0;
}
图的遍历------》邻接表:
本方法注意的一点是dfs()内的sum变量的定义及其位置,sum表示这个连通块中所有边权之和,本题目中建图为无相连通图,所以每增加一条边数据,实际上增加了双向的两条边,为什么要这样呢?如果不建为无向图,则需要多次遍历,因为不知道哪一个节点的根最深。
由于是无向图,故边权加和sum的位置要特别注意
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int M=2020;
unordered_map<string,int>h1,st;
unordered_map<int,string>h2;
int idx;
int h[M],ne[M],e[M],w[M],g[M];
int n,k;
int di;
void add(int a,int b,int c){
e[di]=b;
ne[di]=h[a];
w[di]=c;
h[a]=di++;
}
int dfs(int ver,vector<string>&res){
st[h2[ver]]=1;
int sum=g[ver];
for(int i=h[ver];i!=-1;i=ne[i]){
int j=e[i];
//如果sum放在这里,会把每一条边加一次,答案错误
if(!st[h2[j]]){
res.push_back(h2[j]);
sum+=dfs(h1[h2[j]],res);
}
}
return sum;
}
int main(){
cin>>n>>k;
memset(h,-1,sizeof h);
while(n--){
string a,b;
int c;
cin>>a>>b>>c;
if(!h1.count(a))
h1[a]=++idx;
if(!h1.count(b))
h1[b]=++idx;
h2[h1[a]]=a;
h2[h1[b]]=b;
add(h1[a],h1[b],c);
add(h1[b],h1[a],c);
g[h1[a]]+=c;//这里必须是+=c,否则是替换之前的边权值!!!
g[h1[b]]+=c;
}
vector<pair<string,int>>ans;
for(int i=1;i<=idx;i++){
string t=h2[i];
vector<string>res;
if(!st[t]){
res.push_back(t);
int sum=dfs(i,res);
sum/=2; //这里由于无向图,故要/2
// cout<<t<<' '<<sum<<' '<<res.size()<<endl;
if(res.size()>=3&&sum>k){
int id=i;
for(auto &tt:res){
if(g[h1[tt]]>g[id]){
id=h1[tt];
}
}
ans.push_back({h2[id],(int)res.size()});
}
}
}
sort(ans.begin(),ans.end());
cout<<ans.size()<<endl;
for(auto t:ans){
cout<<t.first<<' '<<t.second<<endl;
}
return 0;
}