UVA-11747 - Heavy Cycle Edges(Kruskal)

题意:给出一个无向图,求出图中每个环中最大的边,并按顺序输出,若没有,输出forest;

分析:根据kruscal的性质可知,当A点的祖先等于B点的祖先时，说明AB两点构成一个环,并且AB之间的边最大．

// File Name: 11747.cpp
// Author: Zlbing
// Created Time: 2013/4/19 22:44:46

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<stack>
#include<cmath>
#include<queue>
using namespace std;
#define CL(x,v); memset(x,v,sizeof(x));
#define INF 0x3f3f3f3f
#define LL long long
#define REP(i,r,n) for(int i=r;i<=n;i++)
#define RREP(i,n,r) for(int i=n;i>=r;i--)

const int MAXN=1e3+100;
int n,m;
struct Edge{
    int m,u,v,cost;
    bool operator <(const Edge& a)const{
        return cost<a.cost;
    }
};
vector<Edge> edges;
int F[MAXN];
int find(int x)
{
    return x==F[x]?x:F[x]=find(F[x]);
}
void kruskal()
{
    for(int i=0;i<n;i++)F[i]=i;
    sort(edges.begin(),edges.end());
    vector<int> ans;
    for(int i=0;i<m;i++)
    {
        Edge e=edges[i];
        int u=e.u;
        int v=e.v;
        int fu=find(u);
        int fv=find(v);
        //printf("u--%d v---%d\n",u,v);
        if(fu!=fv)
        {
            F[fu]=fv;
        }
        else{
            ans.push_back(e.cost);
        }
    }
    if(ans.size()==0)printf("forest\n");
    else{
        sort(ans.begin(),ans.end());
        for(int i=0;i<ans.size();i++)
            if(i==0)
                printf("%d",ans[i]);
            else printf(" %d",ans[i]);
        printf("\n");
    }
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        if(n==0&&m==0)break;
        edges.clear();
        REP(i,0,m-1)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            edges.push_back((Edge){i,a,b,c});
            //edges.push_back((Edge){2*i+1,b,a,c});
        }
        kruskal();
    }
    return 0;
}