11747 - Heavy Cycle Edges Solution

11747 - Heavy Cycle Edges Solution

/*

uva id: shoaib05

Accepted Time: 0.003

Algorithm: Kruskal. 

*/

#include<iostream>

#include<vector>

#include<algorithm>

using namespace std;

typedef pair<int,int> pii;

typedef pair<pii,int>ppi;

vector<ppi> myvec;

int parent[1000],node;

bool mySort(ppi p1,ppi p2)

{

return p1.second<p2.second;

}

int getParent(int n)

{

if(n==parent[n])

return n;

else

return getParent(parent[n]);

}

int main()

{

int u,v,wt,edge,i,j;

pii p1;

ppi p2;

bool flag;

while(cin>>node>>edge)

{

if(node==0 && edge==0)

break;

for(i=0;i<node;i++)

parent[i]=i;

for(i=0;i<edge;i++)

{

cin>>u>>v>>wt;

p1=pair<int,int>(u,v);

p2=pair<pii,int>(p1,wt);

myvec.push_back(p2);

}

sort(myvec.begin(),myvec.end(),mySort);

flag=false;

for(i=0;i<edge;i++)

{

p2=myvec[i];

p1=p2.first;

u=p1.first;

v=p1.second;

u=getParent(u);

v=getParent(v);

if(u==v)

{

if(flag)

cout<<" ";

cout<<p2.second;

flag=true;

}

else if(u>v)

parent[u]=v;

else

parent[v]=u;

}

myvec.clear();

if(!flag)

cout<<"forest";

cout<<endl;

}

return 0;

}