A：黑白边

A:黑白边

• 并查集+贪心
• 贪心：优先读入黑边
• 并查集：存在不连通的情况就合并，并记录白边使用的次数
• 最后，判断是否为一组连通集，如果为一组那么输出白边次数，否则不构成两两连通，输出-1

代码如下：

#include<bits/stdc++.h>

using namespace std;

#define  mm(a,x) memset(a,x,sizeof a)
#define  mk make_pair
#define ll long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define lowbit(x) (x) & (-x)

const int N = 2e5 + 10;

struct Node{
    int a,b,c;
}node[N];

int n,m;
int fa[N];

void init(){
    for(int i = 1; i < N; i ++ ){
        fa[i] = i;
    }
}

int find(int x){
    if(fa[x] != x) fa[x] = find(fa[x]);
    return fa[x];
}

void merge(int a,int b){
    fa[find(a)] = find(b);
}

bool cmp(Node a,Node b){
    return a.c < b.c;
}

int main() {
    init();
    cin >> n >> m;
    for(int i = 0; i < m; i ++ ){
        int a,b,c; cin >> a >> b >> c;
        node[i] = {a,b,c};
    }
    sort(node,node + m,cmp);
    int ans = 0;
    for(int i = 0; i < m; i ++ ){
        int a,b,c;
        a = node[i].a,b = node[i].b; c = node[i].c;
        if(find(a) != find(b)){
            merge(a,b);
            if(c == 1) ans ++;
        }
    }
    set<int > s;
    for(int i = 1; i <= n; i ++ ) s.insert(find(i));
    if(s.size() == 1) cout<<ans;
    else cout<<-1;    
    return 0; 
}