1 /* 2     题意：N个城市中每两个城市有多条路径连接，可是因为路径存在的天数是有限的！以为某条路经不存在了 3     导致N个城市不能连通了，那么村名们就会抗议！问一共会有多少次抗议！ 4      5     思路：最小生成树....我们用最大边来建立树！只要有最大边将节点连接并保证连通！那么边权小的值 6     就可以忽略了！最后将生成树中由（最大边组成的）去重（相同的值只有一次抗议）！这时剩下边的数值就是 7     答案了！  8 */ 9 #include<iostream>10 #include<cstring>11 #include<cstdio>12 #include<algorithm>13 #include<vector>14 #define M 1000515 #define N 10000516 using namespace std;17 struct EDGE{18    int u, v, tt;       19 };20 21 int f[N];22 int n, m;23 int getFather(int x){24    return x==f[x] ? x:f[x]=getFather(f[x]);    25 }26 27 bool Union(int a, int b){28     int fa=getFather(a), fb=getFather(b);29     if(fa!=fb){30        f[fa]=fb;31        return true;32     }     33     return false;34 }35 36 bool cmp(EDGE a, EDGE b){37    return a.tt > b.tt;38 }39 40 EDGE edge[N];41 int xx[N];42 int main(){43    while(scanf("%d%d", &n, &m)!=EOF){44         for(int i=1; i<=n; ++i)45            f[i]=i;46         for(int i=0; i<m; ++i)47            scanf("%d %d %d", &edge[i].u, &edge[i].v, &edge[i].tt);                                48         sort(edge, edge+m, cmp);//将边权按照从大到小排序！ 49         int cnt=0;50         for(int i=0; i<m; ++i)51            if(Union(edge[i].u, edge[i].v)) 52               xx[cnt++]=edge[i].tt;53         cnt=unique(xx, xx+cnt)-xx;//去重 54         printf("%d\n", cnt);55    }56    return 0;    57 }58