// Laboratorio 4 - Esercizio 1
// Matteo Schiff - s295565

#include <stdio.h>
#include <stdlib.h>
#define FILENAME "grafo.txt"

int checkVertexCover(int *soluzione, int N, int **archi, int E) {
    for (int i = 0; i < E; i++) {
        if (soluzione[archi[i][0]] == 0 && soluzione[archi[i][1]] == 0)
            return 0;
    }
    return 1;
}

void vertexCoverR(int pos, int **archi, int E, int *soluzione, int N) {
    if (pos >= N) {
        if (checkVertexCover(soluzione, N, archi, E)) {
            printf("(");
            for (int i = 0; i < N; i++) {
                if (soluzione[i] == 1) {
                    printf("%d,", i);
                }
            }
            printf("\b)\n");
        }
        return;
    }

    soluzione[pos] = 0;
    vertexCoverR(pos+1, archi, E, soluzione, N);
    soluzione[pos] = 1;
    vertexCoverR(pos+1, archi, E, soluzione, N);
}

void vertexCovers(int **archi, int N, int E) {
    int *soluzione = (int *) malloc(N * sizeof(int));
    vertexCoverR(0, archi, E, soluzione, N);
    free(soluzione);
}

void leggiGrafo(int ***archi, int *N, int *E) {
    FILE *fp;

    if ((fp = fopen(FILENAME, "r")) == NULL) {
        printf("Impossibile aprire il file di input %s", FILENAME);
        exit(1);
    }

    fscanf(fp, "%d %d", N, E);
    *archi = (int **) malloc(*E * sizeof(int *));
    if (*archi == NULL) {
        printf("Impossibile allocare memoria");
        exit(2);
    }

    for (int i = 0; i < *E; i++) {
        (*archi)[i] = (int *) malloc(2 * sizeof(int));
        if ((*archi)[i] == NULL) {
            printf("Impossibile allocare memoria");
            exit(2);
        }
        fscanf(fp, "%d %d", &(*archi)[i][0], &(*archi)[i][1]);
    }
    fclose(fp);
}

int main(int argc, char ** argv)
{
    int **archi, N, E;

    leggiGrafo(&archi, &N, &E);
    vertexCovers(archi, N, E);
    free(archi);

    return 0;
}