Matrice di Adiacenza - Rappresentazione di un Grafo

Un grafo è una struttura composta da vertici (nodi) e archi che collegano tali vertici. I grafi possono essere utilizzati per modellare relazioni tra oggetti o per rappresentare una rete. Spesso vengono impiegati per descrivere i collegamenti tra città, persone o anche entità astratte.

I grafi possono essere diretti oppure non diretti:

1. Grafi diretti: Tutti gli archi hanno una direzione, il che significa che esiste una “strada” da un vertice a un altro e non è detto che ci sia il verso opposto. È simile a una strada a senso unico.

   Yet, it’s possible to have both directions in a directed graph. They are just explicitly marked for that (the connection between vertices 5 and 8 in the graph).

1. Grafi non diretti: Gli archi non hanno alcuna direzione, il che implica che se esiste un arco tra due vertici, questi risultano collegati tra loro in entrambi i versi.

Uno dei modi per rappresentare un grafo è attraverso la Matrice di Adiacenza. Si tratta di una matrice quadrata che rappresenta l’intero grafo. Ogni riga e colonna della matrice corrisponde a un vertice del grafo. Se esiste un arco tra due vertici, l’elemento corrispondente nella matrice viene impostato a 1. Altrimenti, è pari a 0.

Ecco un esempio di matrice di adiacenza per il grafo diretto sopra descritto:

g = [
#  1  2  3  4  5  6  7  8
  [0, 1, 0, 1, 0, 0, 0, 0],   # connessioni in uscita dal vertice 1
  [0, 0, 0, 0, 1, 0, 0, 0],   # connessioni in uscita dal vertice 2
  [0, 1, 0, 0, 0, 0, 0, 0],   # connessioni in uscita dal vertice 3
  [0, 0, 0, 0, 0, 0, 0, 0],   # connessioni in uscita dal vertice 4
  [0, 0, 0, 0, 0, 1, 0, 1],   # connessioni in uscita dal vertice 5
  [0, 0, 0, 1, 0, 0, 1, 0],   # connessioni in uscita dal vertice 6
  [0, 0, 0, 0, 0, 0, 0, 1],   # connessioni in uscita dal vertice 7
  [0, 0, 0, 0, 1, 0, 0, 0],   # connessioni in uscita dal vertice 8
]

Si noti che, in caso di arco bidirezionale, entrambi i vertici avranno il valore 1 nelle rispettive posizioni.

Inoltre, vale la pena osservare che abbiamo modificato la numerazione dei vertici. Di conseguenza, se accediamo a g[0], in realtà otteniamo tutte le connessioni del nodo con indice 1. Avremmo potuto usare 9 righe e 9 colonne invece di 8, mantenendo una corrispondenza uno a uno tra i numeri nell’immagine e gli indici nella matrice g, ma la scelta dipende esclusivamente da voi 😎.

Sfida: Da Archi a Matrice di Adiacenza

Dato un grafo con v vertici e e archi, l’obiettivo è costruirne la matrice di adiacenza.

Input

La prima riga di input contiene due interi v (1 ≤ v ≤ 1000) ed e (1 ≤ e ≤ 100 000).

Le successive e righe contengono coppie di interi v1, v2 (1 ≤ v1, v2 ≤ v), indicando che il vertice v1 è collegato al vertice v2 e viceversa.

Output

Il programma deve stampare la matrice di adiacenza corrispondente al grafo fornito in ingresso. I valori in ciascuna riga devono essere separati da uno spazio.

Esempi