[题目大意]
给定一个无向图，求出这些边(至少出现在一棵生成树中的边)的数目。
[解题思路]
理解MST的思想，将贪心思想运用。
由小到大遍历这些边，权值相同的为一组。
先判断这些边是否能够成为树边，再对这些边进行合并。
[注意事项]
不知道为何，以前一直写的模板不顶用了...
一定要改成比较丑的样子...
[Code]
#include<iostream>
#include<cstdio>
#include<algorithm>
#define FF(i,N) for( int i=0;i<N;i++ )
using namespace std;struct edge{int u,v,len;
}E[111111];
int n,m;
int fat[111111];int getf( int x ){if( fat[x]==x ) return x;else return fat[x]=getf(fat[x]);
}bool cmp( edge a,edge b ){ return a.len<b.len; }
int krus()
{sort( E,E+m,cmp );memset( fat,0,sizeof(fat) );for( int i=0;i<=n;i++ ) fat[i]=i;int ret=0,pre=-1;for( int i=0;i<=m;i++ ){if( pre!=-1&&E[pre].len!=E[i].len ){for( int j=pre;j<i;j++ )if( getf(E[j].u)!=getf(E[j].v) )ret++;for( int j=pre;j<i;j++ )fat[getf(E[j].u)]=getf(E[j].v);//fat[fat[(E[j].u]]=fat[E[j].v];pre=-1;}if( pre==-1 )pre=i;}return ret;
}int main()
{int t;scanf("%d",&t);while( t-- ){scanf( "%d %d",&n,&m );E[m].len=INT_MAX;FF(i,m) scanf( "%d%d%d",&E[i].u,&E[i].v,&E[i].len );printf( "%d\n",krus() );}return 0;
}