网易4.16笔试通用技术第三题

#include<bits/stdc++.h>
using namespace std;

class unionSet{
public:
    int *fa, n;
    unionSet(int n) : n(n){
        fa = new int[n + 1];
        for(int i = 0; i <= n; i++) fa[i] = i;
    }
    int find(int x) {return fa[x] = (fa[x] == x ? x : find(fa[x]));}
    void merge(int a, int b){fa[find(a)] = find(b);}
};

struct edge{
    int s, e, v;
};

bool cmp(const edge& a, const edge& b){
    return a.v < b.v;
}


edge edg[200005];
int n, m, cnt, edg_cnt, num[200005], res, sum;

void add_edge(int s, int e){
    int ret = 0;
    edg[edg_cnt].s = s;
    edg[edg_cnt].e = e;
    int t = num[s] * num[e];
    string str = to_string(t);
    for(auto x : str) {
        if(x == '0') ret++;
    }
    edg[edg_cnt].v = ret;
    sum += ret;
    edg_cnt++;
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> num[i];
    }
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        add_edge(a, b);
    }
    sort(edg, edg + m, cmp);
    unionSet u(n);
    for(int i = 0; i < m; i++){
        int s = edg[i].s, e = edg[i].e, v = edg[i].v;
        if(u.find(s) != u.find(e)){
            u.merge(s, e);
            res += v;
            cnt++;
            if(cnt == n - 1){
                cout << sum - res << endl;
                return 0;
            }
        }
    }
    cout << "orz" << endl;
    return 0;
}