GCD Spanning Tree

The first line contains three integers $n, m, k \ (1 \le n, m,k \le 10^5)$ , representing the number of vertices and edges in $G$ , and the number of queries.

For the following $m$ lines, each line contains three integers $u_i,v_i,w_i \ ( 1 \le u_i, v_i \le n, u_i\not = v_i, 1 \le w_i \le 10^6)$ , represents there is an edge in $G$ connects vertices $u_i$ and $v_i$ and its weight is $w_i$ . It's guaranteed that the graph is connected.

For the following $k$ lines, each line contains an integer $x_i \text{ }(1\le x_i \le 10^6)$ , representing the $i$ -th query.

C++(clang++ 11.0.1) 解法, 执行用时: 521ms, 内存消耗: 34116K, 提交时间: 2023-06-09 13:04:18

#include <iostream>
#include <algorithm>
#include <vector>

using i64 = long long;

using namespace std;

const int N = 1000100;

vector<pair<int, int>> e[N];
int ans[N], p[N], res;
int n, m, k;

int find(int x) {
  return x == p[x] ? x : p[x] = find(p[x]);
}

void merge(int u, int v) {
  u = find(u), v = find(v);
  if (u == v) return;
  res--;
  p[u] = v;
}

int main() {
  cin.tie(0)->sync_with_stdio(false);
  cin >> n >> m >> k;   
  int mx = 0;
  for (int i = 1; i <= m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    e[w].emplace_back(u, v);
    mx = max(mx, w);
  }
  for (int i = 1; i <= n; i++) {
    p[i] = i;
  }
  for (int i = 1; i <= mx; i++) {
    res = n - 1;
    for (int j = i; j <= mx; j += i) {
      for (auto& [u, v] : e[j]) {
        merge(u, v);
      }
    }
    ans[i] = res;
    for (int j = i; j <= mx; j += i) {
      for (auto& [u, v] : e[j]) {
        p[u] = u, p[v] = v;
      }
    }
  }
  while (k--) {
    int x;
    cin >> x;
    if (x > mx) cout << n - 1 << '\n';
    else cout << ans[x] << '\n';
  }
  return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 666ms, 内存消耗: 116876K, 提交时间: 2023-06-05 12:40:39

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int mm=3e6+7;
vector<int>fa(1e5+1);
vector<int>bj;
inline void clear(){
	for(auto i:bj)fa[i]=i;
	bj.clear();
}
int cnt;
inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
inline void merge(int x,int y){
	x=find(x),y=find(y);
	if(x==y)return;
	cnt++;
	fa[x]=y;
	bj.push_back(x);
}
vector<pair<int,int>>p[(int)1e6+7];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int n,m,k;
	cin>>n>>m>>k;
    for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		for(int j=1;j<=w/j;j++){
			if(w%j==0){
				p[j].push_back({u,v});
				if(w/j!=j)p[w/j].push_back({u,v});
			}
		}
	}
	vector<int>ans(1e6+1);
	for(int i=1;i<=1e6;i++){
		for(auto [x,y]:p[i]){
			merge(x,y);
		}
		ans[i]=n-1-cnt;
        cnt=0;
		clear();
	}
	while(k--){
		int x;
		cin>>x;
		cout<<ans[x]<<'\n';
	}
}

详情