洛谷P 1525犯罪者を収監(そして捜査集)

トランスファゲート
2人の衝突した犯罪者の間でつながっていて、怒りの値になる権利を持っていて、権利をソートして、それから調査集で処理します.私たちは辺権の大きい辺に2つの点を同じ集合にしないようにしました.衝突すると、現在の辺権は最大の怒り値になります.Code:

#include
#include
#include
using namespace std;

struct node{
    int x,y,c;
    inline bool operatorconst node&b)const
    {
        return c>b.c;
    }
}a[100010];
int n,m,f[20010],b[20010];

inline int findfa(int x)
{
    if(f[x]==x) return x;
    else return f[x]=findfa(f[x]);
}

int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=m;i++)
        scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].c);
    sort(a+1,a+1+m);
    for(int i=1;i<=m+1;i++)
    {
        int fx=findfa(a[i].x),fy=findfa(a[i].y);
        if(fx==fy)
        {
            printf("%d",a[i].c);
            return 0;
        }
        else
        {
            if(!b[a[i].x]) b[a[i].x]=a[i].y;
            else f[findfa(b[a[i].x])]=fy;
            if(!b[a[i].y]) b[a[i].y]=a[i].x;
            else f[findfa(b[a[i].y])]=fx;
        }
    }
    return 0;
}