(UVA) 11747 - Heavy Cycle Edges

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=2847

題目大意：一個圖G(V,E)，找出所有環中的最大值。

那就把MST求出後，輸出所有剩下邊即可。

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;

typedef long long LL;
const int MAX_N = 1004;
const int MAX_M = 25006;

struct Edge {
 int a,b;
 LL c;
} edg[MAX_M];

bool operator<(const Edge &e1,const Edge &e2){
 return e1.c<e2.c;
} 

Edge MP(int _a,int _b,LL _c) {
 Edge ret;
 ret.a=_a;
 ret.b=_b;
 ret.c=_c;
 return ret;
}

struct DisjointSet {
 int p[MAX_N];
 void init(int n) {
  for (int x=0;n>=x;x++) p[x]=x;
 }
 int Find(int x) {
  return p[x]==x?x:p[x]=Find(p[x]);
 }
 void Union(int x,int y) {
  p[Find(x)]=Find(y);
 }
} djs;

bool Kruskal(int n,int m) {
 sort(edg,edg+m);
 djs.init(n);
 bool ret=false;
 for (int i=0;m>i;i++) {
  while (i<m && djs.Find(edg[i].a) == djs.Find(edg[i].b)) {
   if (ret) printf(" %lld",edg[i].c);
   else if (!ret) printf("%lld",edg[i].c);
   i++;
   ret=true;
  }
  djs.Union(edg[i].a,edg[i].b);
 }
 return ret;
}

int main () {
 int n,m;
 while (scanf("%d %d",&n,&m) != EOF) {
  if (n==0 && m==0) break;
  for (int x=0;m>x;x++) {
   int i,j,k;
   scanf("%d %d %d",&i,&j,&k);
   edg[x] = MP(i,j,k);
  }
  if (!Kruskal(n,m)) printf("forest");
  puts("");
 }
}