5128. 带阈值的图连通性
2020-10-18 本文已影响0人
来到了没有知识的荒原
5128. 带阈值的图连通性
这题实际上考的是并查集,以及用类似埃式筛法进行优化。
不优化会tle的
class Solution {
public:
int p[10010];
int find(int a){
if(a!=p[a])p[a]=find(p[a]);
return p[a];
}
void merge(int a,int b){
int roota=find(a),rootb=find(b);
if(roota!=rootb){
p[roota]=rootb;
}
}
vector<bool> areConnected(int n, int threshold, vector<vector<int>>& queries) {
for(int i=1;i<=n;i++)p[i]=i;
for(int k=threshold+1;k<=n;k++){
for(int j=k;j<=n;j+=k){
merge(j,k);
}
}
vector<bool>ans(queries.size());
for(int i=0;i<queries.size();i++){
int a=queries[i][0],b=queries[i][1];
if(find(a)==find(b))ans[i]=(true);
else ans[i]=(false);
}
return ans;
}
};