#include <mpi.h>
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX_ITERATIONS 5

int main(int argc, char** argv) {
    MPI_Init(&argc, &argv);

    int world_rank, world_size;
    MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);
    MPI_Comm_size(MPI_COMM_WORLD, &world_size);

    // Phase 1: Leader Election
    int leader = world_rank;
    for (int iteration = 0; iteration < MAX_ITERATIONS; iteration++) {
        for (int i = 0; i < world_size; i++) {
            if (i != world_rank) {
                MPI_Send(&leader, 1, MPI_INT, i, 0, MPI_COMM_WORLD);
                int received_leader;
                MPI_Recv(&received_leader, 1, MPI_INT, i, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
                if (received_leader > leader) {
                    leader = received_leader;
                }
            }
        }
    }

    // Phase 2: Spanning Tree Construction
    int parent = -1;
    if (world_rank == leader) {
        for (int i = 0; i < world_size; i++) {
            if (i != leader) {
                MPI_Send(&leader, 1, MPI_INT, i, 0, MPI_COMM_WORLD);
            }
        }
    } else {
        MPI_Recv(&parent, 1, MPI_INT, MPI_ANY_SOURCE, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
        for (int i = 0; i < world_size; i++) {
            if (i != world_rank && i != parent) {
                MPI_Send(&leader, 1, MPI_INT, i, 0, MPI_COMM_WORLD);
            }
        }
    }

    // Phase 3: Broadcasting the Tree Structure (Optional)
    int* tree = malloc(world_size * sizeof(int));
    if (world_rank == leader) {
        // Initialize tree structure
        for (int i = 0; i < world_size; i++) {
            tree[i] = -1; // -1 indicates no parent
        }
    } else {
        MPI_Recv(tree, world_size, MPI_INT, parent, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
    }
    tree[world_rank] = parent;

    // Propagate the tree structure to children
    for (int i = 0; i < world_size; i++) {
        if (i != world_rank && i != parent) {
            MPI_Send(tree, world_size, MPI_INT, i, 0, MPI_COMM_WORLD);
        }
    }

    // Display the tree structure
    printf("Process %d: Leader is %d, Parent is %d\n", world_rank, leader, tree[world_rank]);
    for (int i = 0; i < world_size; i++) {
        printf("Process %d: Parent of %d is %d\n", world_rank, i, tree[i]);
    }

    free(tree);
    MPI_Finalize();
    return 0;
}