LightOJ 1012 - Guilty Prince (cpp file)

Problem Type : BFS/DFS


#include<stdio.h>
#include<string.h>
#define MAX 21
int v,e,cou=0;
int X[4]= {-1,0,0,1};
int Y[4]= {0,-1,1,0};
char mat[MAX][MAX];
int color[MAX][MAX];
void dfs(int i,int j)
{
    color[i][j]=1;

    int vx,vy,k;
    for(k=0; k<4; k++)
    {
        vx=X[k]+i;
        vy=Y[k]+j;
        if(vx>=0 && vx<v && vy>=0 && vy<e)
        {
            if(color[vx][vy]==0 && mat[vx][vy]=='.')
            {
                cou++;
                dfs(vx,vy);
            }
        }
    }
}
int main()
{
    int test,i,j,cas=0;
    scanf("%d",&test);
    while(test--)
    {
        cas++;
        scanf("%d %d",&e,&v);
        for(i=0; i<v; i++)
        {
            for(j=0; j<e; j++)
            {
                scanf(" %c",&mat[i][j]);
            }
        }
        memset(color,0,sizeof(color));
        cou=1;
        for(i=0; i<v; i++)
        {
            for(j=0; j<e; j++)
            {
                if(mat[i][j]=='@')
                {
                    dfs(i,j);
                }
            }

        }
        printf("Case %d: %d\n",cas,cou);
    }

}

UVA 10305 - Ordering Tasks(cpp file)

Problem Type : Topological Sort


#include<stdio.h>
#include<vector>
#include<string.h>
#define MAX 102
using namespace std;
vector<int>vcc[MAX],collect;
int color[MAX];
void dfs(int n)
{
    color[n]=1;
    int i;
    for(i=0;i<vcc[n].size();i++)
    {
        if(color[vcc[n][i]]==0)
        {
            dfs(vcc[n][i]);
        }
    }
    collect.push_back(n);
}
int node,edge;
int main()
{
    int n,m,i,j;
    while(scanf("%d %d",&node,&edge)==2)
    {
        if(node==0 && edge==0)
        break;
        memset(color,0,sizeof(color));
        for(i=0; i<MAX; i++)
        {
            vcc[i].clear();
        }
        collect.clear();
        for(i=0; i<edge; i++)
        {
            scanf("%d %d",&n,&m);
            vcc[n].push_back(m);
        }
        for(i=1;i<=node;i++)
        {
           if(color[i]==0)
           {
               dfs(i);
           }
        }
        int len = collect.size();
        printf("%d",collect[len-1]);
        for(i=len-2;i>=0;i--)
        {
            printf(" %d",collect[i]);
        }
        printf("\n");
    }

}

UVA 263 - Number Chains(cpp file)

Problem Type : String




#include<string.h>
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;


int main ()
{
    int n;

    while ( scanf ("%d", &n) && n )
    {
        char num [20];
        int chainLength = 1;
        sprintf (num, "%d", n);
        printf ("Original number was %d\n", n);

        sort (num, num + strlen (num));

        char num2 [20];
        strcpy (num2, num);

        reverse (num2, num2 + strlen (num2));
        int first = atoi (num2);
        int second = atoi (num);
        int subs = first - second;
        printf ("%d - %d = %d\n", first, second, subs);
        map<int ,bool>m;
        while (m[subs]==false )
        {
            m [subs] = true;
            sprintf (num, "%d", subs);
            sort (num, num + strlen (num));
            strcpy (num2, num);
            reverse (num2, num2 + strlen (num2));
            first = atoi (num2);
            second = atoi (num);
            subs = first - second;
            printf ("%d - %d = %d\n", first, second, subs);
            chainLength++;
        }

        printf ("Chain length %d\n\n", chainLength);
    }

    return 0;
}

UVA 10685 - Nature(cpp file)

Problem Type : Disjoint Set Data Structure


#include<stdio.h>
#include<iostream>
#include<map>
#include<string>
#include<algorithm>
#define MAX 50005
using namespace std;
map<string,long >mymap;
long par[MAX],node,edge,store[MAX];
void make_set()
{
    long i;
    for(i=1; i<=node; i++)
    {
        par[i]=i;
    }
}
long find_set(long n)
{
    if(par[n]!=n)
    {
        par[n]=find_set(par[n]);
    }
    return par[n];
}
void Union(long x,long y)
{
    long ux,uy;
    ux= find_set(x);
    uy= find_set(y);
    if(ux!=uy)
    {
        par[ux]=uy;
    }
    else
        return;
}
int main()
{
    long i,j,n,ux,uy;
    string s,p,q;
    while(scanf("%ld %ld",&node,&edge)==2)
    {
        if(node==0 && edge==0)
            break;
        n=0;
        for(i=1; i<=node; i++)
        {
            n++;
            cin >> s;
            mymap[s]=n;
            // printf("%ld",n);

        }
        make_set();
        for(i=1; i<=edge; i++)
        {
            cin >> p >>q;
            long int x = mymap[p];
            long int y= mymap[q];
            Union(x,y);
        }
        long j=0;
        for(i=1; i<=node; i++)
        {
            store[j] =find_set(i);
            j++;
        }
        sort(store,store+j);
        long sum=0,cou,k;
        for(i=0; i<j-1; i++)
        {
            cou=1;
            for(k=i+1;k<j;k++)
            {
                if(store[i]==store[k])
                {
                    cou++;
                }
                else
                {
                    break;
                }
            }
            if(sum<cou)
            {
                sum=cou;
            }
            i=k-1;
        }
        printf("%ld\n",sum);

    }

}

UVA 11503 - Virtual Friends(cpp file)

Problem Type : Disjoint Set Data Structure



#include<stdio.h>
#include<string>
#include<cstring>
#include<iostream>
#include<map>
#define MAX 100001
using namespace std;
long int coun,arr[MAX],par[MAX];
map <string,long >mymap;

void make_set(long int n)
{
    par[n]=n;
    return;
}
long int find_set(long n)
{
    if(par[n]!= n)
    {
        par[n]=find_set(par[n]);
    }
    return par[n]=par[n];
}

long int find_set1(long n)
{
    if(par[n]!=n)
    {
        coun++;
        par[n]=find_set(par[n]);
    }
    return par[n]=par[n];
}
int main()
{
    long int i,j,len,k,node,test,x,y,n;
    string node1,node2;
    scanf("%ld",&test);
    while(test--)
    {
        scanf("%ld",&n);
        node=0;
        mymap.clear();
        memset(par,0,sizeof(par));
        for(i=0; i<MAX; i++)
        {
            arr[i]=1;
        }
        while(n--)
        {
            cin >> node1 >> node2;
            if(mymap.find(node1)==mymap.end())
            {
                node=node+1;
                mymap[node1]=node;
                par[node]=node;

            }
            if(mymap.find(node2)==mymap.end())
            {
                node=node+1;
                mymap[node2]=node;
                par[node]=node;

            }
            x = mymap[node1];
            y = mymap[node2];
            long ux,uy;
            ux=find_set(x);
            uy=find_set(y);
            if(ux==uy)
            {
                printf("%ld\n",arr[ux]);
            }
            else
            {
                par[ux]=uy;
                arr[uy]+=arr[ux];
                printf("%ld\n",arr[uy]);
            }

        }


    }
    return 0;
}

UVA 852 - Deciding victory in Go(cpp file)

Problem Type : DFS



#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAX 10
using namespace std;
char mat[MAX][MAX];
int X[4]= {-1,0,0,1};
int Y[4]= {0,-1,1,0};
int color[MAX][MAX],cou1,cou2,color1[MAX][MAX];
void dfs(int i,int j)
{
  color[i][j]=1;
  cou1++;
  int k,vx,vy;
  for(k=0;k<4;k++)
  {
      vx=i+X[k];
      vy=j+Y[k];
    if(vx>=0 && vx<9 && vy>=0 && vy<9&&(mat[vx][vy]=='O'||mat[vx][vy]=='.'))
    {
        if(color[vx][vy]==0)
        {
            dfs(vx,vy);
        }
    }
  }
}
void dfs1(int i,int j)
{
  color1[i][j]=1;
  cou2++;
  int k,vx,vy;
  for(k=0;k<4;k++)
  {
      vx=i+X[k];
      vy=j+Y[k];
    if(vx>=0 && vx<9 && vy>=0 && vy<9&&((mat[vx][vy]=='.')||(mat[vx][vy]=='X')))
    {
        if(color1[vx][vy]==0)
        {
            dfs1(vx,vy);
        }
    }
  }
}
int main()
{
    int i,j,n,m,test;
    scanf("%d",&test);
    getchar();
    while(test--)
    {
        for(i=0; i<9; i++)
        {
            for(j=0;j<9;j++)
            {
                scanf(" %c",&mat[i][j]);
            }

        }

        memset(color,0,sizeof(color));
        cou1=0;
        cou2=0;
        for(i=0; i<9; i++)
        {
            for(j=0;j<9;j++)
            {
                if(mat[i][j]=='O' && color[i][j]==0)
                {
                    dfs(i,j);
                }
            }

        }
        memset(color1,0,sizeof(color1));
        memset(color,0,sizeof(color));
        cou2=0;
        for(i=0; i<9; i++)
        {
            for(j=0;j<9;j++)
            {
                if(mat[i][j]=='X' && color1[i][j]==0)
                {
                    dfs1(i,j);
                }
            }

        }
       int sum=cou1+cou2;
      int common = sum-81;
      int black = cou2-common;
      int white =cou1-common;
      printf("Black %d White %d\n",black,white);
      memset(mat,'\0',sizeof(mat));
    }
}

UVA 908 - Re-connecting Computer Sites(cpp file)

Problem Type : Minimum Spanning Tree




#include<stdio.h>
#include<algorithm>
#define MAX 1000001
using namespace std;
long par [MAX],n,m,k;
struct node
{
    long node1;
    long node2;
    long cost;
};
node arr[MAX];
void make_set()
{
    long i;
    for(i=1; i<=n; i++)
    {
        par[i]=i;
    }
}
bool comp(node x,node y)
{
    return x.cost <y.cost;
}
long find_set(long n)
{
    if(par[n]!=n)
    {
        par[n]=find_set(par[n]);
    }
    return par[n]=par[n];
}
int main()
{
    long i,j,cas=0,cou,sum,ux,uy,sum1;
    while(scanf("%ld",&n)==1)
    {
        make_set();
         for(i=1; i<n; i++)
         {
             scanf("%ld %ld %ld",&arr[i].node1,&arr[i].node2,&arr[i].cost);

         }
         arr[0].node1=0;
         arr[0].node2=0;
         arr[0].cost=0;
         sum=0;
         cou=0;
         sort(arr,arr+n,comp);
         for(i=1; i<n; i++)
         {
             ux=find_set(arr[i].node1);
             uy=find_set(arr[i].node2);
             if(ux!=uy)
             {
                 par[ux]=uy;
                 cou++;
                 sum+=arr[i].cost;
             }
             if(cou==n)
                 break;
         }

        scanf("%ld",&k);

        arr[0].node1=0;
        arr[0].node2=0;
        arr[0].cost=0;
        for(i=1; i<=k; i++)
        {
            scanf("%ld %ld %ld",&arr[i].node1,&arr[i].node2,&arr[i].cost);
        }
        scanf("%ld",&m);
        for(i=k+1; i<=k+m; i++)
        {
            scanf("%ld %ld %ld",&arr[i].node1,&arr[i].node2,&arr[i].cost);
        }
        long s=k+m+1;
        make_set();
        cou =0;
        sum1=0;
        sort(arr,arr+s,comp);
        for(i=1; i<=s;i++)
        {
            ux=find_set(arr[i].node1);
            uy = find_set(arr[i].node2);
            if(ux!=uy)
            {
                par[ux]=uy;
                cou++;
                sum1+=arr[i].cost;
            }
            if(cou==n)
                break;
        }
        if(cas!=0)
            printf("\n");
        cas++;
        printf("%ld\n%ld\n",sum,sum1);
        }

}

UVA 11953 - Battleships(cpp file)

Problem Type : Graph(DFS)



#include<stdio.h>
#include<string.h>
#define MAX 106
long n,m,coun=0,color[MAX][MAX];
char mat[MAX][MAX];
int X[4]={-1,0,0,1};
int Y[4]={0,-1,1,0};
void dfs(int i,int j)
{
    color[i][j]=1;
    int k,vx,vy;
    for(k=0;k<4;k++)
    {
        vx=X[k]+i;
        vy=Y[k]+j;
        if(vx>=0 && vx<n && vy>=0 && vy<n && (mat[vx][vy]=='x'||mat[vx][vy]=='@'))
        {
            if(color[vx][vy]==0)
            {
                dfs(vx,vy);
            }
        }
    }
}
int main()
{
    int test,i,j,cas=0;
    scanf("%d",&test);
    while(test--)
    {
        cas++;
        scanf("%d",&n);
       memset(mat,'\0',sizeof(mat));
        for(i=0; i<n; i++)
        {
            for(j=0; j<n; j++)
            {
               scanf(" %c",&mat[i][j]);
            }
        }
        memset(color,0,sizeof(color));
         coun=0;
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                if(mat[i][j]=='x' && color[i][j]==0)
                {
                    coun++;
                    dfs(i,j);

                }
            }
        }
        printf("Case %d: %d\n",cas,coun);
    }

}

UVA 11518 - Dominos 2(cpp file)

Problem Type : Graph(DFS)




#include<bits/stdc++.h>
#define MAX 10009
using namespace std;
long node ,edge, call,coun=0,color[MAX];
vector<long >vcc[MAX];
void dfs(long k)
{
    color[k]=1;
    long i;
    for(i=0; i<vcc[k].size(); i++)
    {
        if(color[vcc[k][i]]==0)
        {
            dfs(vcc[k][i]);
        }
    }
}
int main()
{
    long test,v,e,i,call1;
    scanf("%ld",&test);
    while(test--)
    {
        scanf("%ld %ld %ld",&node,&edge,&call);
        for(i=0; i<=MAX; i++)
        {
            vcc[i].clear();
        }
        for(i=0; i<edge; i++)
        {
            scanf("%ld %ld",&v,&e);
            vcc[v].push_back(e);
        }
          memset(color,0,sizeof(color));
        for(i=1; i<=call; i++)
        {
            scanf("%ld",&call1);
             dfs(call1);
        }
        coun=0;
        for(i=1; i<=node; i++)
        {
            if(color[i]==1)
            {
                coun++;
            }
        }
        printf("%ld\n",coun);
    }

}

UVA 11228 - Transportation system.(cpp file)

Problem Type : Minimum Spanning Tree



#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define MAX 2000
#define MAX1 500000
using namespace std;
long par[MAX],n,cost1;
struct node
{
    long node1;
    long node2;
    double cost;
};
node arr[MAX1];
struct cor
{
    long  ux;
    long  uy;
};
cor mat[MAX1];
bool comp(node x,node y)
{
    return x.cost<y.cost;
}
void make_set()
{
    long i;
    for(i=0; i<n; i++)
    {
        par[i]=i;
    }
}
long find_set(long n)
{
    if(par[n]!=n)
    {
        par[n]=find_set(par[n]);
    }
    return par[n];
}
int main()
{

    long int test,i,j,c,xx,yy,state,cas=0,road1,rail1;
    double px,py,road,rail;
    scanf("%ld",&test);
    while(test--)
    {
        cas++;
        scanf("%ld %ld",&n,&cost1);
        make_set();
        for(i=0; i<n; i++)
        {
           scanf("%ld %ld",&mat[i].ux,&mat[i].uy);
        }
        c=0;
        for(i=0; i<n-1; i++)
        {
            for(j=i+1; j<n; j++)
            {
                px= (double)(pow((mat[i].ux-mat[j].ux),2));
                py= (double)(pow((mat[i].uy-mat[j].uy),2));
                arr[c].cost=sqrt(px+py);
                arr[c].node1=i;
                arr[c].node2=j;
                c++;
            }
        }
        sort(arr,arr+c,comp);
        state=1;
        rail=0;
        road=0;
        for(i=0; i<c; i++)
        {
            xx=find_set(arr[i].node1);
            yy=find_set(arr[i].node2);
            if(xx!=yy && arr[i].cost>cost1)
            {
                par[xx]=yy;
                rail+=arr[i].cost;
                state++;
            }
            else if(xx!=yy)
            {
                par[xx]=yy;
                road+=arr[i].cost;
            }
        }
        road1=floor(road+.5);
        rail1=floor(rail+.5);
        printf("Case #%ld: %ld %ld %ld\n",cas,state,road1,rail1);
    }
}

UVA 10608 - Friends(cpp file)

Problem Type : Disjoint Set Data-Structure




#include<bits/stdc++.h>
#define MAX 500000
#define MAX1 30000
using namespace std;
long par[MAX1];
long n,m,color[MAX1];
void make_set()
{
    long i;
    for(i=1; i<=n; i++)
    {
        par[i]=i;
    }
}
long find_set(long n1)
{
    if(par[n1]!=n1)
    {
        par[n1]=find_set(par[n1]);
    }
    return par[n1]=par[n1];
}
void Union(long p,long q)
{
    long ux = find_set(p);
    long uy = find_set(q);
    if(ux!=uy)
    {
        par[ux]=uy;
    }
}
int main()
{
    long test,i,j,v,e,store[MAX1],sum;
    scanf("%ld",&test);
    while(test--)
    {
        scanf("%ld %ld",&n,&m);
        make_set();
        for(i=1; i<=m; i++)
        {
            scanf("%ld %ld",&v,&e);
            Union(v,e);
        }
        store[0]=0;
        for(i=1; i<=n; i++)
        {
         long   ux=find_set(i);
            store[i]=ux;
        }
        sort(store,store+n+1);
        long  c=0,sum=0;
        for(i=1; i<n; i++)
        {
            c=0;
            for(j=i+1; j<=n; j++)
            {
                if(store[i]==store[j])
                {
                    c++;
                }
                else
                   break;
            }
            i=j-1;
            if(sum<c)
            {
                sum=c+1;
            }
        }
        printf("%ld\n",sum);
    }
}

UVA 10473 - Simple Base Conversion(cpp file)

Problem Type : Number Theory



#include<bits/stdc++.h>
#define MAX 100
using namespace std;
int main()
{

    long i,j,k,n,dec,len,hex,mod;
    char ch[MAX],hexa[MAX];
    while(gets(ch))
    {
        if(ch[0]=='-')
        {
            break;
        }

        len=strlen(ch);
        if(ch[0]=='0' && ch[1]=='x')
        {
            dec=0;
            k=len-3;
            for(i=2; i<len; i++)
            {
                if(ch[i]=='A')
                {
                    dec=dec+10*pow(16,k);
                }
                else if(ch[i]=='B')
                {
                    dec+=11*pow(16,k);
                }
                else if(ch[i]=='C')
                {
                    dec+=12*pow(16,k);
                }
                else if(ch[i]=='D')
                {
                    dec+=13*pow(16,k);
                }
                else if(ch[i]=='E')
                {
                    dec+=14*pow(16,k);
                }
                else if(ch[i]=='F')
                {
                    dec+=15*pow(16,k);
                }
                else
                {

                    int x=ch[i]-48;
                    dec+= x*pow(16,k);

                }

                k--;
            }
            printf("%ld\n",dec);

        }
        else
        {
            hex=atoi(ch);
            int m=0;
            for(i=0; ;i++)
            {

                mod=hex%16;
                hex=hex/16;
                if(mod==10)
                {
                    hexa[m]='A';
                    m++;
                }
                else if(mod==11)
                {
                    hexa[m]='B';
                    m++;
                }
                else if(mod==12)
                {
                    hexa[m]='C';
                    m++;
                }
                else if(mod==13)
                {
                    hexa[m]='D';
                    m++;
                }
                else if(mod==14)
                {
                    hexa[m]='E';
                    m++;
                }
                else if(mod==15)
                {
                    hexa[m]='F';
                    m++;
                }
                else
                {
                    hexa[m]=mod +48;
                    m++;
                }
                if(hex==0)
                    break;

            }
            printf("0x");
            for(i=m-1;i>=0;i--)
            {
                printf("%c",hexa[i]);
            }
            printf("\n");
        }
    }

}

UVA 11733 - Airports(cpp file)

Problem Type : Graph(Minimum Spanning Tree)




#include<bits/stdc++.h>
#define MAX 100005
using namespace std;
long par[MAX],n,m,cost1;
struct node
{
    long node1;
    long node2;
    long cost;
};
node arr[MAX];
void make_set()
{
    long i;
    for(i=1; i<=n; i++)
    {
        par[i]=i;
    }
}
long find_set(long n)
{
    if(par[n]!=n)
    {
        par[n]=find_set(par[n]);
    }
    return par[n]=par[n];
}
bool comp(node x,node y)
{
    return x.cost < y.cost;
}
int main()
{
    long int i,j,len,test,ux,uy,airport,cas=0;
    long long sum;
    scanf("%ld",&test);
    while(test--)
    {
        cas++;
        cost1=0;
        scanf("%ld %ld %ld",&n,&m,&cost1);
        arr[0].node1=0;
        arr[0].node2=0;
        arr[0].cost=0;
        for(i=1; i<=m; i++)
        {
            scanf("%ld %ld %ld",&arr[i].node1,&arr[i].node2,&arr[i].cost);
        }

        sort(arr,arr+(m+1),comp);
        make_set();
        long cou=0;
        sum=0;
        airport=0;
        for(i=1; i<=m; i++)
        {
            ux=find_set(arr[i].node1);
            uy=find_set(arr[i].node2);

            if(ux!=uy)
            {
                //  printf("\n\n%ld %ld\n",arr[i].node1,arr[i].node2);
                cou++;
                par[ux]=uy;
                if(arr[i].cost>=cost1)
                {
                    sum+=cost1;
                    airport++;
                }
                else
                {
                    sum+=arr[i].cost;
                }

            }
            if(cou==n)
                break;

        }

        for(i=1; i<=n; i++)
        {
            if(par[i]==i)
            {
                sum+=cost1;
                airport++;
            }
        }
        printf("Case #%ld: %lld %ld\n",cas,sum,airport);

    }

}

UVA 10550 - Combination Lock(cpp file)

Problem Type : Ad hoc



#include<bits/stdc++.h>
int main()
{
int a,b,c,d,sum,p,q,r,x;
while(scanf("%d %d %d %d",&a ,&b,&c,&d)==4)
{
    if(a==0 && b==0 && c==0 && d==0)
        break;
        p=a;
        q=b;
        r=c;
        x=d;
    if(a<b)
    {
        p=a+40;
    }
    sum=(p-q)*9;
    if(c<b)
    {
        r=r+40;
    }
    sum+=abs(r-q)*9;
    r=c;
    if(c<d)
    {
        r=r+40;
    }
    sum+=abs(r-x)*9;
    //printf("%d\n",sum);
printf("%d\n",sum+1080);
}

}

UVA 11857 - Driving Range(cpp file)

Problem Type : Graph(Minimum Spanning Tree)




#include<bits/stdc++.h>
#define MAX 1000001
using namespace std;
long par[MAX],n,m,color[MAX];

struct node
{
    long node1;
    long node2;
    long  cost;
};
node arr[MAX];
void make_set()
{
    long i;
    for(i=0; i<n; i++)
    {
        par[i]=i;
    }
}
bool comp(node x, node y)
{
    return x.cost<y.cost;
}
long find_set(long n)
{
    if(par[n]!=n)
    {
        par[n]=find_set(par[n]);
    }
    return par[n]=par[n];
}
int main()
{
    long i,j,k,ux,uy;
    while(scanf("%ld %ld",&n,&m)==2)
    {
        if(n==0 && m==0)
        {
            break;
        }
        //printf("%d\n",m);
        for(i=0;i<m;i++)
        {
            scanf("%ld %ld %ld",&arr[i].node1,&arr[i].node2,&arr[i].cost);
        }
        make_set();
        sort(arr,arr+m,comp);
        long s=0,cou=0;

        for(i=0; i<m; i++)
        {
            ux=find_set(arr[i].node1);
            uy=find_set(arr[i].node2);
            if(ux!=uy)
            {
                cou++;
                par[ux]=uy;
                s=arr[i].cost;
            }
            if(cou==n)
                break;

        }
        long vx;
        cou=0;
        ux=find_set(0);
        for(i=1; i<n; i++)
        {
            vx=find_set(i);
            if(ux!=vx)
            {
                printf("IMPOSSIBLE\n");
                cou=1;
                break;
            }

        }
        if(cou==0)
        {
            printf("%ld\n",s);
        }

    }
}

UVA 11747 - Heavy Cycle Edges

Problem Type :  Graph(Minimum Spanning Tree)



#include<bits/stdc++.h>
#define MAX 25001
#define MAX1 1001
using namespace std;
struct node
{
    long node1;
    long node2;
    long cost;
};
long int par[MAX1],n,m;
node arr[MAX];
void make_set()
{
    long i;
    for(i=0; i<n; i++)
    {
        par[i]=i;
    }
}
long find_set(long n)
{
    if(par[n]!=n)
    {
        par[n]=find_set(par[n]);
    }
    return par[n]=par[n];
}
bool comp(node x,node y)
{
    return x.cost < y.cost;
}
int main()
{
    long int i,j,k,cou,ux,uy,px,py,l=0,collect[MAX];
    while(scanf("%ld %ld",&n,&m)==2)
    {
        if(n==0 && m==0)
            break;
        for(i=0; i<m; i++)
        {
            scanf("%ld%ld%ld",&arr[i].node1,&arr[i].node2 ,&arr[i].cost);
        }
        make_set();
        sort(arr,arr+m,comp);
        cou=0;
        l=0;
        for(i=0; i<m; i++)
        {
            ux=find_set(arr[i].node1);
            uy=find_set(arr[i].node2);
            if(ux!=uy)
            {
                par[ux]=uy;

            }
            else
            {
                collect[l]= arr[i].cost;
                l++;
                cou=1;
            }
        }
        if(cou==1)
        {
            for(i=0; i<l-1; i++)
            {
                printf("%ld ",collect[i]);
            }
            printf("%ld\n",collect[l-1]);
        }
        else
        {
            printf("forest\n");
        }

    }
}