// ------------------------------------------------------
// ---- TODOS OS CAMINHOS ENTRE DOIS VERTICES -----------
// ------------------------------------------------------
#include <iostream>
#include <fstream>
#include <cmath>
#include <ctime>
#include <climits>
#include <windows.h>
#include <queue>
#include <list>
using namespace std;


typedef struct vertice {
    int grau;
    list<int> AdjL;
} vertice;

typedef struct digraph {
	int N;// numero de vertices
	int M;// numero de arestas
	vertice* V;
} digraph;


// --------------------------------------------------
// Todos os caminhos entre dois vertices de s para t
// --------------------------------------------------
void all_paths(digraph& G, int s, int t);


// ---------------------------------------
// Manutenção de grafos
// ---------------------------------------
int digraph_create(digraph& G);
void digraph_delete(digraph& G);


// ------------------------------------------------------
// ------ MAIN ------------------------------------------
// ------------------------------------------------------
int main() {
    digraph G;
    if (!digraph_create(G)) {cout<<"Arquivo inexistente"; return -1;}

    //all_paths(G,7,0);
    all_paths(G,0,15);

    digraph_delete(G);
    return 0;
}


// ------------------------------------------------------
// ------------------------------------------------------
// ------------------------------------------------------
void print_path(list<int>& path) {
    list<int>::iterator it;
    for (it=path.begin(); it!=path.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

int nao_pertence(int x, list<int>& path) {
    list<int>::iterator it;
    for (it=path.begin(); it!=path.end(); ++it) {
        if (*it == x) return 0;
    }
    return 1;
}

// -------------------------------------------
// --- ALGORITMO PRINCIPAL -------------------
// --- Semelhante a Busca em Largura ---------
// -------------------------------------------
void all_paths(digraph& G, int ini, int fim) {
    list<int>::iterator it;
    list<int> path;
    queue<list<int> > Fila;
    path.push_back(ini);
    Fila.push(path);

    while (! Fila.empty()) {
        path = Fila.front();  Fila.pop();
        int ult = (*path.rbegin());// ultimo do caminho
        if (ult == fim) print_path(path);
        else {
            for (it=G.V[ult].AdjL.begin(); it!=G.V[ult].AdjL.end(); ++it) {
                int w = (*it);
                if (nao_pertence(w, path)) {
                    list<int> newpath(path);
                    newpath.push_back(w);
                    Fila.push(newpath);
                }
            }
        }
    }
}


// ------------------------------------------------------
// ---- MANUTENÇÃO DE GRAFOS ----------------------------
// ------------------------------------------------------


// ------------------------------------------------------
// ------------------------------------------------------
int digraph_create(digraph& G) {
    ifstream arq;
    arq.open("entrada_allpaths_adjL.txt");
    if (arq.fail()) return 0;
    arq >> G.N;
    G.M=0; G.V = NULL;
    G.V = new vertice[G.N];

    for (int x=0; x<G.N; x++) {
        int grau;
        arq >> grau;
        G.V[x].grau = grau;
        G.M += grau;
        for (int i=1; i<=grau; i++) {
            int y;
            arq >> y;
            G.V[x].AdjL.push_back(y);
        }
    }
    arq.close();
    return 1;
}
// ------------------------------------------------------
// ------------------------------------------------------
void digraph_delete(digraph& G) {
    delete[] G.V;
    G.V = NULL;
}