#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>

/***************Partie union-find***************/
struct uf {
    int taille; //nombre d'éléments dans la partition
    int* classes; //a nécessairement taille cases
};
typedef struct uf uf;

//Renvoie le minimum de deux entiers
int min(int i, int j)
{
    if (i<j) {return i;}
    else {return j;}
}

//Permet d'afficher le contenu d'un tableau tab d'entiers de taille n
void afficher_tableau(int* tab, int n)
{
    for (int i = 0; i < n; i++)
    {
        printf("%d ", tab[i]);
    }
    printf("\n");
}











/***************Partie construction de labyrinthes***************/
struct graphe {
    int cote; //taille du côté du labyrinthe
    int nb_sommets; //nombre de sommets correspondant = cote*cote
    bool** aretes; //matrice d'adjacence de taille nb_sommets*nb_sommets
};
typedef struct graphe graphe;

//Intialise un graphe de côté n donc à n^2 sommets ne contenant aucune arête.
graphe* initialiser_graphe(int n)
{
    graphe* g = (graphe*)malloc(sizeof(graphe));
    int ns = n*n;
    g->cote = n;
    g->nb_sommets = ns;
    g->aretes = (bool**)malloc(ns*sizeof(bool*));
    for (int i = 0; i < ns; i++)
    {
        g->aretes[i] = (bool*)malloc(ns*sizeof(bool));
        for (int j = 0; j < ns; j++)
        {
            g->aretes[i][j] = false;
        }
    }
    return g;
}

//Libération de graphe.
void liberer_graphe(graphe* g)
{
    for(int i = 0; i < g->nb_sommets; i++)
    {
        free(g->aretes[i]);
    }
    free(g->aretes);
    free(g);
}

//Fonction d'affichage d'une matrice de booléens de taille n*n
void afficher_matrice(bool** mat, int n)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            printf("%d ", mat[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}



void coordonnees(int sommet, int n, int* i, int* j)
{ 

 /************************ A IMPLEMENTER ************************/

}

//Indique si les sommets u et v sont cote à cote dans une grille de côté n.
//ATTENTION : Nécessite d'avoir implémenté la fonction coorodnnées pour fonctionner correctement.
bool sont_cote_a_cote(int n, int u, int v)
{
    int iu, iv, ju, jv;
    coordonnees(u,n,&iu,&ju);
    coordonnees(v,n,&iv,&jv);
    if (iu == iv)
    {
        if(ju == 0)
        {
            return (jv == ju +1);
        }
        if (ju == n-1)
        {
            return (jv == ju -1);
        }
        else
        { 
            return (jv == ju +1) || (jv == ju -1);
        }
    }
    else if (ju == jv)
    {
        if(iu == 0)
        {
            return (iv == iu +1);
        }
        if (iu == n-1)
        {
            return (iv == iu -1);
        }
        else
        { 
            return (iv == iu +1) || (iv == iu -1);
        }
    }
    else
    {
        return false; 
    }
}

//Créé une permutation aléatoire sigma de [0,n-1]. La case i du tableau renvoyé contient sigma(i).
//Il n'est pas nécessaire de comprendre son fonctionnement précis.
int* melanger(int n)
{
    int* permutation = (int*)malloc(n*sizeof(int));
    for (int i = 0; i < n ; i++)
    {
        permutation[i] = i;
    }
    for (int i = 0; i < n; i++)
    {
        int pos_alea = rand () % (i+1); //On suppose que cette instruction s'exécute en temps O(1).
        int tmp = permutation[pos_alea];
        permutation[pos_alea] = permutation[i];
        permutation[i] = tmp;
    }
    return permutation;
}

//Création de labyrinthe
graphe* creer_laby(int n)
{
    int nb_sommets = n*n;
    int nb_aretes = nb_sommets*nb_sommets; 
    int* aretes_alea = melanger(nb_aretes); //Mélange autant d'entiers qu'il y a d'arêtes dans un labyrinthe de côté n

    for (int i = 0; i < nb_aretes; i++)
    {
        //On admet que les trois instructions suivantes stockent dans les variables u et v les extrémités de la i-ème arête tirée aléatoirement. 
        int id_arete = aretes_alea[i];
        int u, v;
        coordonnees(id_arete, nb_sommets, &u, &v); 
      
    }

    return NULL; //A retirer après complétion de la fonction.

}





int main()
{
    srand(0);
    // Faire vos tests après cette ligne.


    return 0;
}