UVa 11747 - Heavy Cycle Edges

  1  /*
  2  Problem type: Graph - MST
  3  Algorithm: Find the Minimum Spanning Tree (MST) (using Kruskal,
  4      Prim) and print out all the edges which are not included in the MST.
  5  */
  6  #include <iostream>
  7  #include <cstdio>
  8  #include <cstring>
  9  #include <cmath>
 10  #include <cstdlib>
 11  #include <vector>
 12  #include <algorithm>
 13  
 14  using namespace std;
 15  
 16  class Edge {
 17  public:
 18      int a,b,t;
 19  
 20      Edge(int u, int v, int value) {
 21          a = u;
 22          b = v;
 23          t = value;
 24      }
 25  
 26      bool operator>(const Edge &edge) const {
 27          return this->t > edge.t;
 28      }
 29      bool operator<(const Edge &edge) const {
 30          return this->t < edge.t;
 31      }
 32      bool operator==(const Edge &edge) const {
 33          return this->t == edge.t;
 34      }
 35  };
 36  
 37  vector<Edge> eList;
 38  vector<int> fa, result;
 39  vector<bool> isInSpanningTree;
 40  int n,m;
 41  
 42  bool readFile();
 43  bool ok(int a, int b);
 44  void solve();
 45  
 46  int main() {
 47      while (readFile()) {
 48          solve();
 49          eList.clear();
 50      }
 51      return 0;
 52  }
 53  
 54  bool readFile() {
 55      cin >> n >> m;
 56      if (n == 0 && m == 0) return false;
 57      for (int i = 1; i <= m; i++) {
 58          int u,v,w;
 59          cin >> u >> v >> w;
 60          eList.push_back(Edge(u,v,w));
 61      }
 62  
 63      return true;
 64  }
 65  
 66  bool ok(int a, int b) {
 67      while (a != fa[a]) a = fa[a];
 68      while (b != fa[b]) b = fa[b];
 69      if (a == b) return false;
 70      else {
 71          if (a < b) fa[b] = a;
 72          else fa[a] = b;
 73      }
 74      return true;
 75  }
 76  
 77  void solve() {
 78      fa.assign(n, 0);
 79      for (int i = 0; i < n; i++) fa[i] = i;
 80      isInSpanningTree.assign(m+1, false);
 81      result.clear();
 82  
 83      sort(eList.begin(), eList.end());
 84  
 85      int cnt = 0;
 86      for (int i = 0; i < (int)eList.size(); i++) {
 87          if (ok(eList[i].a, eList[i].b)) {
 88              cnt++;
 89              isInSpanningTree[i] = true;
 90              if (cnt == n-1) break;
 91          }
 92      }
 93  
 94      for (int i = 0; i < (int)eList.size(); i++) {
 95          if (!isInSpanningTree[i]) result.push_back(eList[i].t);
 96      }
 97  
 98      sort(result.begin(), result.end());
 99      if (result.size() != 0) {
100          for (int i = 0; i < (int)result.size(); i++) {
101              if (i < (int)result.size() - 1) cout << result[i] << " ";
102              else cout << result[i] << endl;
103          }
104      } else {
105          cout << "forest" << endl;
106      }
107  }
108  
109