redotica.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define TAM 128
#define INF (0x3f3f3f3f)

int adj[TAM][TAM],v[TAM],min[TAM],p[TAM],n,m;

int prim(int k) {
    int next = -1, tmin = 1000;
    register int i;
    v[k] = 1;
    for (i = 1; i <= n; i++)
        if (!v[i]) {
            if (adj[k][i] < min[i])
                min[i] = adj[k][i], p[i] = k;
            if (min[i] < tmin)
                tmin = min[i], next = i;
        }
    if (next != -1) {
        if (p[next] > next)
            printf("%d %d\n", next, p[next]);
        else
            printf("%d %d\n", p[next], next);
        prim(next);
    }
}
int main(){
    int x,y,z,i,j,teste=1;
    while(scanf("%d%d", &n, &m) && n){
        for (i = 1; i <= n;i++){
            v[i] = 0;
            min[i] = INF;
            for (j = 1; j <= n; j++){
                adj[i][j] = INF;
            }
        }
        while (m--){
            scanf("%d%d%d",&x,&y,&z);
            adj[x][y] = adj[y][x] = z;            
        }
        printf("Teste %d\n",teste++);
        prim(1);
        printf("\n");
    }
    return 0;
}