C++(clang++11) 解法, 执行用时: 46ms, 内存消耗: 3848K, 提交时间: 2021-02-24 08:06:13

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

int L=0,x[200005],y[200005],V[200005];
int find(int a)
{
	if(a==V[a])return a;
	return V[a]=find(V[a]);
}
int main()
{
	int i,a,b,n,m,z,s=0,ans=0;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)V[i]=i;
	while(m--)
	{
		scanf("%d%d%d",&x[L],&y[L],&z);
		if(z)L++;
		else 
		{
			a=find(x[L]),b=find(y[L]);
			if(a!=b)s++,V[a]=b;
		}
	}
	for(i=0;i<L;i++)
	{
		a=find(x[i]),b=find(y[i]);
		if(a!=b)s++,ans++,V[a]=b;
	}
	if(s!=n-1)ans=-1;
	printf("%d\n",ans);
    return 0;
}