// Depth-First-Durchlauf eines Graphen
// (mit nummerieren und eintragen des eingehenden Knotengrades)
// Hauptprogramm zum Ergänzen
//
// Aufruf: dfs knotenzahl startknoten
//
// Klaus Kusche, 2019

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

// struct "node" für einen Knoten
// "in_cnt" für die Anzahl eingehender Kanten
// "dfs_nr" für die Nummer des Knotens in DFS-Reihenfolge
// "edges" für die Kantenliste
/*** missing ***/

// struct "edge" für eine Kante (mit "neighbor" und "next")
/*** missing ***/

// Rekursive DFS-Durchlauf-Funktion:
// wird mit dem aktuellen Knoten
// und der ersten zu vergebenden DFS-Nummer aufgerufen
// macht rekursiven DFS-Durchlauf der Knoten,
// befüllt dabei "in_cnt" und "dfs_nr"
// Voraussetzung: Bei Aufruf ist "dfs_nr" in allen Knoten -1 und "in_cnt" 0
// Returnwert: Die erste nicht vergebene DFS-Nummer
/*** missing ***/


int main(int argc, const char *argv[])
{
  unsigned int count, start;  // Knotenanzahl & Nummer des Ausgangsknotens
  node *nodes;      // Pointer auf dyn. Array aller Nodes
  int neighb;       // Eingelesene Nummer des Nachbar-Knotens
  edge **link;      // Zum hinten Anhängen an die Adjazenzliste mit **-Trick
  edge *e;
  node *startnode;  // Pointer auf Ausgangsknoten
  
  if (argc != 3) {
    fprintf(stderr, "Usage: %s node_count starting_node_number\n", argv[0]);
    exit(EXIT_FAILURE);
  }

  count = (unsigned int) atoi(argv[1]);
  start = (unsigned int) atoi(argv[2]);

  if ((count < 1) || (start >= count)) {
    fprintf(stderr,
            "Usage: %s node_count starting_node_number\n"
            "       (node_count > 0, 0 <= starting_node_number < node_count\n",
            argv[0]);
    exit(EXIT_FAILURE);
  }

  nodes = (node *) (malloc(count * sizeof(node)));
  if (nodes == NULL) {
    fprintf(stderr, "%s: out of memory\n", argv[0]);
    exit(EXIT_FAILURE);
  }

  for (node *p = nodes; p < nodes + count; ++p) {
    p->in_cnt = 0;
    p->dfs_nr = -1;
    p->edges = NULL;
    // link zeigt auf den Pointer, in dem die nächste Kante eingetragen wird
    link = &(p->edges);
    printf("Adjazenzen von Knoten %u eingeben (0...%u, -1 = Ende):\n",
           (unsigned int)(p - nodes), // liefert Nummer des Knotens in nodes
           count - 1);
    for (;;) {
      if (scanf("%d", &neighb) != 1) {
        fprintf(stderr, "%s: invalid input\n", argv[0]);
        exit(EXIT_FAILURE);
      }
      if (neighb < 0) break;
      if ((unsigned int) neighb >= count) {
        fprintf(stderr, "%s: invalid input\n", argv[0]);
        exit(EXIT_FAILURE);
      }
      e = (edge *) (malloc(sizeof(edge)));
      if (e == NULL) {
        fprintf(stderr, "%s: out of memory\n", argv[0]);
        exit(EXIT_FAILURE);
      }
      e->neighbor = &(nodes[neighb]);  // Pointer auf den Zielknoten
      e->next = NULL;                  // Kante wird letzter Knoten der Liste
      // hinten an Adjazenzliste anhängen, nicht vorne:
      // Reihenfolge der Nachbarn aus der Eingabe soll erhalten bleiben!
      *link = e;
      link = &(e->next);
    }
  }

  // Aufruf von dfs
  startnode = &(nodes[start]);
  printf("Verarbeitete Knoten: %d\n", dfs(startnode, 0));

  // Ausgabe
  for (node *p = nodes; p < nodes + count; ++p) {
    printf("Knoten %u: DFS-Nummer %d, In-Count %d\n",
           (unsigned int) (p - nodes), // liefert Nummer des Knotens in nodes
           p->dfs_nr, p->in_cnt);
  }
}