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

#define MAX_SIZE 100

void genconn ( int *C[], int n )
{
    int E[MAX_SIZE], i, j, k, cnt;

    for (i=0; i<n; ++i) {
        cnt = 0;
        for (j=i+1; j<n; ++j)
            cnt += (E[j] = rand() % 2);
        C[i] = (int *)malloc((cnt + 1) * sizeof(int));
        C[i][0] = cnt;
        k = 1;
        for (j=i+1; j<n; ++j) {
            if (E[j]) { C[i][k] = j; ++k; }
        }
    }
}

void prnconn ( int *C[], int n )
{
    int i, j, cnt;

    for (i=0; i<n; ++i) {
        printf("%3d -> ", i);
        cnt = C[i][0];
        for (j=1; j<=cnt; ++j) printf("%3d ", C[i][j]);
        printf("\n");
    }
}

int prnpaths ( int *C[], int n, int src, int dst, int pos, int path[],
               int len, int npaths )
{
    int cnt, j;

    if (pos == dst) {
        ++npaths;
        printf("Path %3d: %d", npaths, src);
        for (j=0; j<len; ++j) printf(" -> %d", path[j]);
        printf("\n");
        return npaths;
    }

    cnt = C[pos][0];
    for (j=1; j<=cnt; ++j) if (C[pos][j] <= dst) {
        path[len] = C[pos][j];
        npaths = prnpaths(C,n,src,dst,path[len],path,len+1,npaths);
    }

    return npaths;
}

int main ( )
{
    int n, *C[MAX_SIZE], s, d, P[MAX_SIZE], m;

    srand((unsigned int)time(NULL));

    printf("n = "); scanf("%d", &n);
    printf("\n");

    genconn(C,n);
    prnconn(C,n);

    printf("\n");
    printf("s = "); scanf("%d", &s);
    printf("d = "); scanf("%d", &d);
    printf("\n");

    m = prnpaths(C,n,s,d,s,P,0,0);
    printf("\n%d paths found\n", m);

    exit(0);
}