/media/sda-magnetic/david/Dokumente-16-2024-08-01/informatikUmathematik/excerpt20240906before/progs2sources20240801/robertsedgewickgraph01.c

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

#define maxV    50

struct node {
    int v;
    struct node *next;
};

int i, j, x, y, V, E;
char v1, v2;

struct node *t, *z;

struct node *adj [maxV];
int a  [maxV][maxV];

int idx (char ch) {
    return ((ch & 0xff) - 'a');
}

void adjmatrix (void) {
        scanf ("%d %d\n", &V, &E);
        for (x = 1;  x <= V;  x++)
            for (y = 1;  y <=  V;  y++)
                a[x] [y] = 0;
        for (x = 1;   x <= V;  x++)
            a [x][x] = 1;
        for (j = 1;  j <= E;  j++) {
            scanf ("%c %c\n", &v1, &v2);
            x = idx (v1);
            y = idx (v2);
            a [x][y] = 1;
            a [y][x] = 1;
        }
}

void adjlist (void) {
    printf ("(|V|,|E|): ");
    scanf ("%d %d", &V, &E);
    z = (struct node *) malloc (sizeof *z);
    z->next = z;

    for (j = 1;  j <= V;  j++) adj [j] = z;
    for (j = 1;  j <= E;  j++) {
        printf ("(x, y): ");
        scanf ("%i %i", &x, &y);
        /*x = idx (v1);
        y = idx (v2);*/
        printf ("%i %i\n", x, y);
        t = (struct node *) malloc (sizeof *t);
        t -> v = x;
        t -> next = adj [y];
        adj [y] = t;
        t = (struct node *) malloc (sizeof *t);
        t -> v = y;
        t -> next = adj [x];
        adj [x] = t;

    }
}

void adjlist_prnt (struct node * t) {
    if (t == z) {
        printf (" empty\n");
        return;
    }
    else {
        printf ("%i ", t->v);
        adjlist_prnt (t->next);
    }
}


void adjlist_print () {

    for (j = 1;  j <= V;  j++) {
        adjlist_prnt (adj [j]);
    }

}


int val [maxV];
int id = 0;

void visit (int k) {
    struct node *t;

    val [k] = ++id;

    for (t = adj [k];  t != z;  t = t->next)
        if (val [t->v] == 0)
            visit (t->v);
}

void listdfs () {
    int k;
    for (k = 1;  k <= V; k++)
        val [k] = 0;
    for (k = 1;  k <= V; k++)
        if (val [k] == 0) {
            printf ("%i, ", k);
            visit (k);
        }
}

int main (void) {
    adjlist ();
    adjlist_print ();
    listdfs ();
}