NYOJ 925 国王的烦恼

从最后一天开始往前加边。

同一天的边同时加到图上，加完之后检查集合数量是否和没加之前有变化。

有变化的话，答案就+1.

 
#include<cstdio>
#include <iostream>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

const int maxn=100000+10;
int n,m;

struct Edge
{
    int u,v,c;
}e[maxn];
int f[maxn];

bool cmp(const Edge&a,const Edge&b)
{
    return a.c>b.c;
}

int Find(int x)
{
    if(x!=f[x]) return f[x]=Find(f[x]);
    return f[x];
}

int main()
{
    while(~scanf("%d%d",&n,&m)){
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].c);
    sort(e+1,e+1+m,cmp);

    for(int i=1;i<=n;i++) f[i]=i;

    int L=1,R=1,ans=0;

    while(1)
    {
        while(1)
        {
            if(e[R].c==e[L].c) R++;
            else break;
        }

        int d=0;
        for(int i=L;i<=R-1;i++)
        {
            int fu=Find(e[i].u);
            int fv=Find(e[i].v);
            if(fu!=fv) d=1,f[fu]=fv;

        }

        ans=ans+d;
        L=R; if(L>m) break;
    }

    printf("%d
",ans);
    }
    return 0;
}