# Eulerweg Eulerkreis

# Dieser Algorithmus liefert eine Entscheidung, ob ein ungerichteter
# zusammenhaengender Graph einen Eulerweg oder einen Eulerkreis
# oder keinen von beiden besitzt.

# Voraussetzungen: 
# Die n Knoten des Graphen werden fortlaufend mit 0, 1, 2, . . . , n-1 bezeichnet.
# Die Kanten des Graphen sind ungerichtet, so dass
# die Adjazenzmatrix symmetrisch ist: a[i][j] = a[j][i],  0 <= i,j <= n-1
# Der Graph enthaelt keine Schlingen als Kanten,
# folglich besteht die Diagonale der Adjazenzmatrix aus lauter Nullen.

# a = [[0] * m for i in range(n)]
# erzeugt eine zweidimensionale Liste mit n Komponenten, wobei jede dieser
# Komponenten ihrerseits eine Liste mit m Komponenten ist; jede Komponente
# a[i][j], 0 <= i <= n-1, 0 <= j <= m-1, erhaelt den Wert 0 zugewiesen.
# i = Zeilenindex, j = Spaltenindex

ans = 'y'

while ans == 'y':

  n = int(input('Anzahl der Knoten: '))

# Erzeugen einer n x n - Matrix mit lauter Nullen
  a = [[0] * n for i in range(n)]

# Eingabe der Adjazenzmatrix
  for i in range(n):
   for j in range(i+1,n):
      print('a(',i,',',j,') = ', end = "")
      a[i][j] = int(input())
      a[j][i] = a[i][j]

# Ausgabe der Adjazenzmatrix
  print('Adjazenzmatrix:')
  print(a)
  for i in range(n): print(a[i])

# Berechnung des Grades von jedem der n Knoten
# Der Grad eines jeden der n Knoten wird in der
# aus n Komponenten bestehenden Liste g abgelegt.
  g = [0]*n   # Erzeugen der Liste g mit lauter Nullen
  for i in range(n):
   for j in range(n): g[i] = g[i] + a[i][j]

# Ausgabe des Grades eines jeden Knotens
  print('Knotengrade:')
  print(g)
  print()

# Decision according to Euler's Theorem
  anzahl = 0
  for i in range(n):
   if g[i] % 2 != 0: anzahl = anzahl + 1

  if anzahl == 0 or anzahl == 2:
    if anzahl == 0:
      print('Der Grad jedes Knotens ist geradzahlig,')
      print('folglich hat der Graph einen Eulerkreis.')
    else:
      print('Der Grad von genau zwei Knoten ist ungerade,')
      print('folglich besitzt der Graph einen Eulerweg,');
      print('aber keinen Eulerkreis.')
      
  else:
    if anzahl == 1: print('Da ',anzahl,' Knoten einen ungeraden Grad hat,')
    else:           print('Da ',anzahl,' Knoten einen ungeraden Grad haben,')
    print('besitzt der Graph weder einen Eulerkreis noch einen Eulerweg.')


  print('\n')
  ans = input('Neuer Graph? <y> <n> ')
  print('\n')