Lezione 12 Grafi

Roberto Trani

roberto.trani@di.unipi.it

Lezione 12 Grafi

Pagina web del corso

http://didawiki.cli.di.unipi.it/doku.php/informatica/all-b/start

Grafi

0

1 2

3 4

5

Matrice di adiacenza

0

1 2

3

4

5

Matrice di adiacenza

M

0 1 0

0 0 0

0 0 0 0

0 1

0 0 0

0 1 0

0 1 0

0 1 0

1

0 0 0

0 0

1

0 0

1

0 0

0

1 2

3

4

0 1 2 3 4 5

5

1 0

2

3

4

5

Matrice di adiacenza

M

0 1 0

0 0 0

0 0 0 0

0 1

0 0 0

0 1 0

0 1 0

0 1 0

1

0 0 0

0 0

1

0 0

1

0 0

0

1 2

3

4 5

int ** M = (int **) malloc(N*sizeof(int *));

for (int i=0; i<N; ++i) {

M[i] = (int *) malloc(N*sizeof(int));

}

Matrice di adiacenza

M

0 1 0

0 0 0

0 0 0 0

0 1

0 0 0

0 1 0

0 1 0

0 1 0

1

0 0 0

0 0

1

0 0

1

0 0

0

1 2

3

4 5

int ** M = (int **) malloc(N*sizeof(int *));

for (int i=0; i<N; ++i) {

M[i] = (int *) malloc(N*sizeof(int));

}

Troppi zeri…

Liste di adiacenza

0

1 2

3

4

5

Liste di adiacenza

E

0

1 2

3

4

5

Liste di adiacenza

E

5 /

0

1 2

3

4

5

Liste di adiacenza

E

0 3 4 /

5 /

0

1 2

3

4

5

Liste di adiacenza

E

0 3 4 /

5 /

/

0

1 2

3

4

5

Liste di adiacenza

E

0 3 4 /

4 5 /

5 /

/

0

1 2

3

4

5

Liste di adiacenza

E

0 3 4 /

4 5 /

5 /

2 /

/

0

1 2

3

4

5

Liste di adiacenza

E

0 3 4 /

4 5 /

5 /

2 /

0 /

/

0

1 2

3

4

5

Liste di adiacenza

E

0 3 4 /

4 5 /

5 /

2 /

typedef struct _edge { struct _edge * next;

int nodeid;

} edge;

edge ** E = (edge **) malloc(N*sizeof(edge *));

0 /

/

0

1 2

3

4 5

/* lista di adiacenza, ogni elemento nella lista rappresenta un arco */

/* array di N liste di adiacenza */

Liste di adiacenza

E

0 3 4 /

4 5 /

5 /

2 /

typedef struct _edge { struct _edge * next;

int nodeid;

} edge;

edge ** E = (edge **) malloc(N*sizeof(edge *));

0 /

/

0

1 2

3

4 5

Troppi salti in memoria…

Liste di adiacenza compatte

0

1 2

3

4

5

E

Liste di adiacenza compatte

5 1

0 3 4

3

4 5

2

2 1

0 /

1 0

0

1 2

3

4

5

E

Liste di adiacenza compatte

typedef struct _edges { int num_edges;

int * edges;

} edges;

edges *E = (edges *) malloc(N*sizeof(edges));

5 1

0 3 4

3

4 5

2

2 1

0 /

1 0

0

1 2

3

4 5

/* per ogni vertice v del grafo, la struct edges memorizza il grado (uscente) e l’array dei vertici

adiacenti a v (che rappresentano gli archi uscenti da v) */

// l’intero grafo è rappresentato tramite un array di edges

E

Liste di adiacenza compatte

typedef struct _edges { int num_edges;

int * edges;

} edges;

edges *E = (edges *) malloc(N*sizeof(edges));

5 1

0 3 4

3

4 5

2

2 1

0 /

1 0

0

1 2

3

4 5

I grafi dinamici possono essere realizzati usando vettori dinamici, o ridimensionabili


— algoritmo dimezza e raddoppia… —

Lettura grafo da input

Lettura grafo da input

Negli esercizi sarà richiesto di leggere un file avente il seguente formato:

Grafo bipartito

Esercizio

Scrivere un programma che legga da tastiera un grafo indiretto e stampi 1 se il grafo `e bipartito, 0 altrimenti. Il grafo `e rappresentato nel seguente formato: la prima riga contiene il numero n di nodi, le successive n righe contengono, per ciascun nodo i, con 0 i < n, il numero ni di archi uscenti da i seguito da una lista di ni nodi destinazione, rappresentati con i numeri [0, n). Si assuma che l’input contenga un grafo indiretto, e quindi che per ciascun arco da i a j esista anche l’arco da j ad i.

Un grafo bipartito `e un grafo tale che l’insieme dei suoi vertici si pu`o partizionare in due sottoinsiemi in cui ogni vertice `e collegato solo a vertici appartenenti alla partizione opposta.

Suggerimento: un grafo `e bipartito se e solo se `e possibile colorarlo usan- do due colori. Colorare il grafo corrisponde ad assegnare a ciascun vertice un colore diverso da quello dei suoi vertici adiacenti.

L’input `e costituito da:

• una riga contenente il numero n di nodi del grafo;

• n righe, una per ciasun nodo i, con i 2 [0, n), nel seguente formato:

– numero n_i di archi uscenti da i;

– lista di n_i nodi destinazione, rappresentati con i numeri [0, n).

L’output contiene una riga contenente 1 se il grafo `e bipartito, 0 altrimenti.

Esempio

Input

5 (numero di elementi)

2 1 3 3 0 2 4 2 1 3 3 0 2 4 2 1 3

Output 1

1

// grado di i

// vertici adiacenti a i

Lettura grafo da input

Negli esercizi sarà richiesto di leggere un file avente il seguente formato:

Grafo bipartito

Esercizio

Scrivere un programma che legga da tastiera un grafo indiretto e stampi 1 se il grafo `e bipartito, 0 altrimenti. Il grafo `e rappresentato nel seguente formato: la prima riga contiene il numero n di nodi, le successive n righe contengono, per ciascun nodo i, con 0 i < n, il numero ni di archi uscenti da i seguito da una lista di ni nodi destinazione, rappresentati con i numeri [0, n). Si assuma che l’input contenga un grafo indiretto, e quindi che per ciascun arco da i a j esista anche l’arco da j ad i.

Un grafo bipartito `e un grafo tale che l’insieme dei suoi vertici si pu`o partizionare in due sottoinsiemi in cui ogni vertice `e collegato solo a vertici appartenenti alla partizione opposta.

Suggerimento: un grafo `e bipartito se e solo se `e possibile colorarlo usan- do due colori. Colorare il grafo corrisponde ad assegnare a ciascun vertice un colore diverso da quello dei suoi vertici adiacenti.

L’input `e costituito da:

• una riga contenente il numero n di nodi del grafo;

• n righe, una per ciasun nodo i, con i 2 [0, n), nel seguente formato:

– numero n_i di archi uscenti da i;

– lista di n_i nodi destinazione, rappresentati con i numeri [0, n).

L’output contiene una riga contenente 1 se il grafo `e bipartito, 0 altrimenti.

Esempio

Input

5 (numero di elementi)

2 1 3 3 0 2 4 2 1 3 3 0 2 4 2 1 3

Output 1

1

Esempio:

6 1 5 3 0 3 4 0

2 4 5

1 2

1 0

Lettura grafo da input

Negli esercizi sarà richiesto di leggere un file avente il seguente formato:

Grafo bipartito

Esercizio

Scrivere un programma che legga da tastiera un grafo indiretto e stampi 1 se il grafo `e bipartito, 0 altrimenti. Il grafo `e rappresentato nel seguente formato: la prima riga contiene il numero n di nodi, le successive n righe contengono, per ciascun nodo i, con 0 i < n, il numero ni di archi uscenti da i seguito da una lista di ni nodi destinazione, rappresentati con i numeri [0, n). Si assuma che l’input contenga un grafo indiretto, e quindi che per ciascun arco da i a j esista anche l’arco da j ad i.

Un grafo bipartito `e un grafo tale che l’insieme dei suoi vertici si pu`o partizionare in due sottoinsiemi in cui ogni vertice `e collegato solo a vertici appartenenti alla partizione opposta.

Suggerimento: un grafo `e bipartito se e solo se `e possibile colorarlo usan- do due colori. Colorare il grafo corrisponde ad assegnare a ciascun vertice un colore diverso da quello dei suoi vertici adiacenti.

L’input `e costituito da:

• una riga contenente il numero n di nodi del grafo;

• n righe, una per ciasun nodo i, con i 2 [0, n), nel seguente formato:

– numero n_i di archi uscenti da i;

– lista di n_i nodi destinazione, rappresentati con i numeri [0, n).

L’output contiene una riga contenente 1 se il grafo `e bipartito, 0 altrimenti.

Esempio

Input

5 (numero di elementi)

2 1 3 3 0 2 4 2 1 3 3 0 2 4 2 1 3

Output 1

1

Esempio:

6 1 5 3 0 3 4 0

2 4 5

1 2

1 0

E

Lettura grafo da input

Negli esercizi sarà richiesto di leggere un file avente il seguente formato:

Grafo bipartito

Esercizio

Scrivere un programma che legga da tastiera un grafo indiretto e stampi 1 se il grafo `e bipartito, 0 altrimenti. Il grafo `e rappresentato nel seguente formato: la prima riga contiene il numero n di nodi, le successive n righe contengono, per ciascun nodo i, con 0 i < n, il numero ni di archi uscenti da i seguito da una lista di ni nodi destinazione, rappresentati con i numeri [0, n). Si assuma che l’input contenga un grafo indiretto, e quindi che per ciascun arco da i a j esista anche l’arco da j ad i.

Un grafo bipartito `e un grafo tale che l’insieme dei suoi vertici si pu`o partizionare in due sottoinsiemi in cui ogni vertice `e collegato solo a vertici appartenenti alla partizione opposta.

Suggerimento: un grafo `e bipartito se e solo se `e possibile colorarlo usan- do due colori. Colorare il grafo corrisponde ad assegnare a ciascun vertice un colore diverso da quello dei suoi vertici adiacenti.

L’input `e costituito da:

• una riga contenente il numero n di nodi del grafo;

• n righe, una per ciasun nodo i, con i 2 [0, n), nel seguente formato:

– numero n_i di archi uscenti da i;

– lista di n_i nodi destinazione, rappresentati con i numeri [0, n).

L’output contiene una riga contenente 1 se il grafo `e bipartito, 0 altrimenti.

Esempio

Input

5 (numero di elementi)

2 1 3 3 0 2 4 2 1 3 3 0 2 4 2 1 3

Output 1

1

Esempio:

6 1 5 3 0 3 4 0

2 4 5

1 2

1 0

E

Lettura grafo da input

Negli esercizi sarà richiesto di leggere un file avente il seguente formato:

Grafo bipartito

Esercizio

Scrivere un programma che legga da tastiera un grafo indiretto e stampi 1 se il grafo `e bipartito, 0 altrimenti. Il grafo `e rappresentato nel seguente formato: la prima riga contiene il numero n di nodi, le successive n righe contengono, per ciascun nodo i, con 0 i < n, il numero ni di archi uscenti da i seguito da una lista di ni nodi destinazione, rappresentati con i numeri [0, n). Si assuma che l’input contenga un grafo indiretto, e quindi che per ciascun arco da i a j esista anche l’arco da j ad i.

Un grafo bipartito `e un grafo tale che l’insieme dei suoi vertici si pu`o partizionare in due sottoinsiemi in cui ogni vertice `e collegato solo a vertici appartenenti alla partizione opposta.

Suggerimento: un grafo `e bipartito se e solo se `e possibile colorarlo usan- do due colori. Colorare il grafo corrisponde ad assegnare a ciascun vertice un colore diverso da quello dei suoi vertici adiacenti.

L’input `e costituito da:

• una riga contenente il numero n di nodi del grafo;

• n righe, una per ciasun nodo i, con i 2 [0, n), nel seguente formato:

– numero n_i di archi uscenti da i;

– lista di n_i nodi destinazione, rappresentati con i numeri [0, n).

L’output contiene una riga contenente 1 se il grafo `e bipartito, 0 altrimenti.

Esempio

Input

5 (numero di elementi)

2 1 3 3 0 2 4 2 1 3 3 0 2 4 2 1 3

Output 1

1

Esempio:

6 1 5 3 0 3 4 0

2 4 5

1 2

1 0

E

Lettura grafo da input

1

Negli esercizi sarà richiesto di leggere un file avente il seguente formato:

Grafo bipartito

Esercizio

Scrivere un programma che legga da tastiera un grafo indiretto e stampi 1 se il grafo `e bipartito, 0 altrimenti. Il grafo `e rappresentato nel seguente formato: la prima riga contiene il numero n di nodi, le successive n righe contengono, per ciascun nodo i, con 0 i < n, il numero ni di archi uscenti da i seguito da una lista di ni nodi destinazione, rappresentati con i numeri [0, n). Si assuma che l’input contenga un grafo indiretto, e quindi che per ciascun arco da i a j esista anche l’arco da j ad i.

Un grafo bipartito `e un grafo tale che l’insieme dei suoi vertici si pu`o partizionare in due sottoinsiemi in cui ogni vertice `e collegato solo a vertici appartenenti alla partizione opposta.

Suggerimento: un grafo `e bipartito se e solo se `e possibile colorarlo usan- do due colori. Colorare il grafo corrisponde ad assegnare a ciascun vertice un colore diverso da quello dei suoi vertici adiacenti.

L’input `e costituito da:

• una riga contenente il numero n di nodi del grafo;

• n righe, una per ciasun nodo i, con i 2 [0, n), nel seguente formato:

– numero n_i di archi uscenti da i;

– lista di n_i nodi destinazione, rappresentati con i numeri [0, n).

L’output contiene una riga contenente 1 se il grafo `e bipartito, 0 altrimenti.

Esempio

Input

5 (numero di elementi)

2 1 3 3 0 2 4 2 1 3 3 0 2 4 2 1 3

Output 1

1

Esempio:

6 1 5 3 0 3 4 0

2 4 5

1 2

1 0

E

Lettura grafo da input

1

Negli esercizi sarà richiesto di leggere un file avente il seguente formato:

Grafo bipartito

Esercizio

Scrivere un programma che legga da tastiera un grafo indiretto e stampi 1 se il grafo `e bipartito, 0 altrimenti. Il grafo `e rappresentato nel seguente formato: la prima riga contiene il numero n di nodi, le successive n righe contengono, per ciascun nodo i, con 0 i < n, il numero ni di archi uscenti da i seguito da una lista di ni nodi destinazione, rappresentati con i numeri [0, n). Si assuma che l’input contenga un grafo indiretto, e quindi che per ciascun arco da i a j esista anche l’arco da j ad i.

Un grafo bipartito `e un grafo tale che l’insieme dei suoi vertici si pu`o partizionare in due sottoinsiemi in cui ogni vertice `e collegato solo a vertici appartenenti alla partizione opposta.

Suggerimento: un grafo `e bipartito se e solo se `e possibile colorarlo usan- do due colori. Colorare il grafo corrisponde ad assegnare a ciascun vertice un colore diverso da quello dei suoi vertici adiacenti.

L’input `e costituito da:

• una riga contenente il numero n di nodi del grafo;

• n righe, una per ciasun nodo i, con i 2 [0, n), nel seguente formato:

– numero n_i di archi uscenti da i;

– lista di n_i nodi destinazione, rappresentati con i numeri [0, n).

L’output contiene una riga contenente 1 se il grafo `e bipartito, 0 altrimenti.

Esempio

Input

5 (numero di elementi)

2 1 3 3 0 2 4 2 1 3 3 0 2 4 2 1 3

Output 1

1

Esempio:

6 1 5 3 0 3 4 0

2 4 5 1 2 1 0

5

E

Lettura grafo da input

1

Negli esercizi sarà richiesto di leggere un file avente il seguente formato:

Grafo bipartito

Esercizio

Scrivere un programma che legga da tastiera un grafo indiretto e stampi 1 se il grafo `e bipartito, 0 altrimenti. Il grafo `e rappresentato nel seguente formato: la prima riga contiene il numero n di nodi, le successive n righe contengono, per ciascun nodo i, con 0 i < n, il numero ni di archi uscenti da i seguito da una lista di ni nodi destinazione, rappresentati con i numeri [0, n). Si assuma che l’input contenga un grafo indiretto, e quindi che per ciascun arco da i a j esista anche l’arco da j ad i.

Un grafo bipartito `e un grafo tale che l’insieme dei suoi vertici si pu`o partizionare in due sottoinsiemi in cui ogni vertice `e collegato solo a vertici appartenenti alla partizione opposta.

Suggerimento: un grafo `e bipartito se e solo se `e possibile colorarlo usan- do due colori. Colorare il grafo corrisponde ad assegnare a ciascun vertice un colore diverso da quello dei suoi vertici adiacenti.

L’input `e costituito da:

• una riga contenente il numero n di nodi del grafo;

• n righe, una per ciasun nodo i, con i 2 [0, n), nel seguente formato:

– numero n_i di archi uscenti da i;

– lista di n_i nodi destinazione, rappresentati con i numeri [0, n).

L’output contiene una riga contenente 1 se il grafo `e bipartito, 0 altrimenti.

Esempio

Input

5 (numero di elementi)

2 1 3 3 0 2 4 2 1 3 3 0 2 4 2 1 3

Output 1

1

Esempio:

6 1 5 3 0 3 4 0

2 4 5 1 2 1 0

5

E

Lettura grafo da input

1 3

Negli esercizi sarà richiesto di leggere un file avente il seguente formato:

Grafo bipartito

Esercizio

Scrivere un programma che legga da tastiera un grafo indiretto e stampi 1 se il grafo `e bipartito, 0 altrimenti. Il grafo `e rappresentato nel seguente formato: la prima riga contiene il numero n di nodi, le successive n righe contengono, per ciascun nodo i, con 0 i < n, il numero ni di archi uscenti da i seguito da una lista di ni nodi destinazione, rappresentati con i numeri [0, n). Si assuma che l’input contenga un grafo indiretto, e quindi che per ciascun arco da i a j esista anche l’arco da j ad i.

Un grafo bipartito `e un grafo tale che l’insieme dei suoi vertici si pu`o partizionare in due sottoinsiemi in cui ogni vertice `e collegato solo a vertici appartenenti alla partizione opposta.

Suggerimento: un grafo `e bipartito se e solo se `e possibile colorarlo usan- do due colori. Colorare il grafo corrisponde ad assegnare a ciascun vertice un colore diverso da quello dei suoi vertici adiacenti.

L’input `e costituito da:

• una riga contenente il numero n di nodi del grafo;

• n righe, una per ciasun nodo i, con i 2 [0, n), nel seguente formato:

– numero n_i di archi uscenti da i;

– lista di n_i nodi destinazione, rappresentati con i numeri [0, n).

L’output contiene una riga contenente 1 se il grafo `e bipartito, 0 altrimenti.

Esempio

Input

5 (numero di elementi)

2 1 3 3 0 2 4 2 1 3 3 0 2 4 2 1 3

Output 1

1

Esempio:

6 1 5 3 0 3 4 0

2 4 5 1 2 1 0

5

E

Lettura grafo da input

1 3

Negli esercizi sarà richiesto di leggere un file avente il seguente formato:

Grafo bipartito

Esercizio

Scrivere un programma che legga da tastiera un grafo indiretto e stampi 1 se il grafo `e bipartito, 0 altrimenti. Il grafo `e rappresentato nel seguente formato: la prima riga contiene il numero n di nodi, le successive n righe contengono, per ciascun nodo i, con 0 i < n, il numero ni di archi uscenti da i seguito da una lista di ni nodi destinazione, rappresentati con i numeri [0, n). Si assuma che l’input contenga un grafo indiretto, e quindi che per ciascun arco da i a j esista anche l’arco da j ad i.

Un grafo bipartito `e un grafo tale che l’insieme dei suoi vertici si pu`o partizionare in due sottoinsiemi in cui ogni vertice `e collegato solo a vertici appartenenti alla partizione opposta.

Suggerimento: un grafo `e bipartito se e solo se `e possibile colorarlo usan- do due colori. Colorare il grafo corrisponde ad assegnare a ciascun vertice un colore diverso da quello dei suoi vertici adiacenti.

L’input `e costituito da:

• una riga contenente il numero n di nodi del grafo;

• n righe, una per ciasun nodo i, con i 2 [0, n), nel seguente formato:

– numero n_i di archi uscenti da i;

– lista di n_i nodi destinazione, rappresentati con i numeri [0, n).

L’output contiene una riga contenente 1 se il grafo `e bipartito, 0 altrimenti.

Esempio

Input

5 (numero di elementi)

2 1 3 3 0 2 4 2 1 3 3 0 2 4 2 1 3

Output 1

1

Esempio:

6 1 5 3 0 3 4 0

2 4 5 1 2 1 0

0 3 4

5

E

Lettura grafo da input

1 3

Negli esercizi sarà richiesto di leggere un file avente il seguente formato:

Grafo bipartito

Esercizio

Scrivere un programma che legga da tastiera un grafo indiretto e stampi 1 se il grafo `e bipartito, 0 altrimenti. Il grafo `e rappresentato nel seguente formato: la prima riga contiene il numero n di nodi, le successive n righe contengono, per ciascun nodo i, con 0 i < n, il numero ni di archi uscenti da i seguito da una lista di ni nodi destinazione, rappresentati con i numeri [0, n). Si assuma che l’input contenga un grafo indiretto, e quindi che per ciascun arco da i a j esista anche l’arco da j ad i.

Un grafo bipartito `e un grafo tale che l’insieme dei suoi vertici si pu`o partizionare in due sottoinsiemi in cui ogni vertice `e collegato solo a vertici appartenenti alla partizione opposta.

Suggerimento: un grafo `e bipartito se e solo se `e possibile colorarlo usan- do due colori. Colorare il grafo corrisponde ad assegnare a ciascun vertice un colore diverso da quello dei suoi vertici adiacenti.

L’input `e costituito da:

• una riga contenente il numero n di nodi del grafo;

• n righe, una per ciasun nodo i, con i 2 [0, n), nel seguente formato:

– numero n_i di archi uscenti da i;

– lista di n_i nodi destinazione, rappresentati con i numeri [0, n).

L’output contiene una riga contenente 1 se il grafo `e bipartito, 0 altrimenti.

Esempio

Input

5 (numero di elementi)

2 1 3 3 0 2 4 2 1 3 3 0 2 4 2 1 3

Output 1

1

Esempio:

6 1 5 3 0 3 4 0

2 4 5 1 2 1 0

0 3 4

5

E

Lettura grafo da input

1 3 0 /

Negli esercizi sarà richiesto di leggere un file avente il seguente formato:

Grafo bipartito

Esercizio

Scrivere un programma che legga da tastiera un grafo indiretto e stampi 1 se il grafo `e bipartito, 0 altrimenti. Il grafo `e rappresentato nel seguente formato: la prima riga contiene il numero n di nodi, le successive n righe contengono, per ciascun nodo i, con 0 i < n, il numero ni di archi uscenti da i seguito da una lista di ni nodi destinazione, rappresentati con i numeri [0, n). Si assuma che l’input contenga un grafo indiretto, e quindi che per ciascun arco da i a j esista anche l’arco da j ad i.

Un grafo bipartito `e un grafo tale che l’insieme dei suoi vertici si pu`o partizionare in due sottoinsiemi in cui ogni vertice `e collegato solo a vertici appartenenti alla partizione opposta.

Suggerimento: un grafo `e bipartito se e solo se `e possibile colorarlo usan- do due colori. Colorare il grafo corrisponde ad assegnare a ciascun vertice un colore diverso da quello dei suoi vertici adiacenti.

L’input `e costituito da:

• una riga contenente il numero n di nodi del grafo;

• n righe, una per ciasun nodo i, con i 2 [0, n), nel seguente formato:

– numero n_i di archi uscenti da i;

– lista di n_i nodi destinazione, rappresentati con i numeri [0, n).

L’output contiene una riga contenente 1 se il grafo `e bipartito, 0 altrimenti.

Esempio

Input

5 (numero di elementi)

2 1 3 3 0 2 4 2 1 3 3 0 2 4 2 1 3

Output 1

1

Esempio:

6 1 5 3 0 3 4 0

2 4 5 1 2 1 0

0 3 4

5

E

Lettura grafo da input

1 3 0 /

Negli esercizi sarà richiesto di leggere un file avente il seguente formato:

Grafo bipartito

Esercizio

Scrivere un programma che legga da tastiera un grafo indiretto e stampi 1 se il grafo `e bipartito, 0 altrimenti. Il grafo `e rappresentato nel seguente formato: la prima riga contiene il numero n di nodi, le successive n righe contengono, per ciascun nodo i, con 0 i < n, il numero ni di archi uscenti da i seguito da una lista di ni nodi destinazione, rappresentati con i numeri [0, n). Si assuma che l’input contenga un grafo indiretto, e quindi che per ciascun arco da i a j esista anche l’arco da j ad i.

Un grafo bipartito `e un grafo tale che l’insieme dei suoi vertici si pu`o partizionare in due sottoinsiemi in cui ogni vertice `e collegato solo a vertici appartenenti alla partizione opposta.

Suggerimento: un grafo `e bipartito se e solo se `e possibile colorarlo usan- do due colori. Colorare il grafo corrisponde ad assegnare a ciascun vertice un colore diverso da quello dei suoi vertici adiacenti.

L’input `e costituito da:

• una riga contenente il numero n di nodi del grafo;

• n righe, una per ciasun nodo i, con i 2 [0, n), nel seguente formato:

– numero n_i di archi uscenti da i;

– lista di n_i nodi destinazione, rappresentati con i numeri [0, n).

L’output contiene una riga contenente 1 se il grafo `e bipartito, 0 altrimenti.

Esempio

Input

5 (numero di elementi)

2 1 3 3 0 2 4 2 1 3 3 0 2 4 2 1 3

Output 1

1

Esempio:

6 1 5 3 0 3 4 0

2 4 5 1 2 1 0

0 3 4

5

E

Lettura grafo da input

1 3

2 0 /

Negli esercizi sarà richiesto di leggere un file avente il seguente formato:

Grafo bipartito

Esercizio

Scrivere un programma che legga da tastiera un grafo indiretto e stampi 1 se il grafo `e bipartito, 0 altrimenti. Il grafo `e rappresentato nel seguente formato: la prima riga contiene il numero n di nodi, le successive n righe contengono, per ciascun nodo i, con 0 i < n, il numero ni di archi uscenti da i seguito da una lista di ni nodi destinazione, rappresentati con i numeri [0, n). Si assuma che l’input contenga un grafo indiretto, e quindi che per ciascun arco da i a j esista anche l’arco da j ad i.

Un grafo bipartito `e un grafo tale che l’insieme dei suoi vertici si pu`o partizionare in due sottoinsiemi in cui ogni vertice `e collegato solo a vertici appartenenti alla partizione opposta.

Suggerimento: un grafo `e bipartito se e solo se `e possibile colorarlo usan- do due colori. Colorare il grafo corrisponde ad assegnare a ciascun vertice un colore diverso da quello dei suoi vertici adiacenti.

L’input `e costituito da:

• una riga contenente il numero n di nodi del grafo;

• n righe, una per ciasun nodo i, con i 2 [0, n), nel seguente formato:

– numero n_i di archi uscenti da i;

– lista di n_i nodi destinazione, rappresentati con i numeri [0, n).

L’output contiene una riga contenente 1 se il grafo `e bipartito, 0 altrimenti.

Esempio

Input

5 (numero di elementi)

2 1 3 3 0 2 4 2 1 3 3 0 2 4 2 1 3

Output 1

1

Esempio:

6 1 5 3 0 3 4 0

2 4 5 1 2 1 0

0 3 4

5

E

Lettura grafo da input

1 3

2 0 /

Negli esercizi sarà richiesto di leggere un file avente il seguente formato:

Grafo bipartito

Esercizio

Scrivere un programma che legga da tastiera un grafo indiretto e stampi 1 se il grafo `e bipartito, 0 altrimenti. Il grafo `e rappresentato nel seguente formato: la prima riga contiene il numero n di nodi, le successive n righe contengono, per ciascun nodo i, con 0 i < n, il numero ni di archi uscenti da i seguito da una lista di ni nodi destinazione, rappresentati con i numeri [0, n). Si assuma che l’input contenga un grafo indiretto, e quindi che per ciascun arco da i a j esista anche l’arco da j ad i.

Un grafo bipartito `e un grafo tale che l’insieme dei suoi vertici si pu`o partizionare in due sottoinsiemi in cui ogni vertice `e collegato solo a vertici appartenenti alla partizione opposta.

Suggerimento: un grafo `e bipartito se e solo se `e possibile colorarlo usan- do due colori. Colorare il grafo corrisponde ad assegnare a ciascun vertice un colore diverso da quello dei suoi vertici adiacenti.

L’input `e costituito da:

• una riga contenente il numero n di nodi del grafo;

• n righe, una per ciasun nodo i, con i 2 [0, n), nel seguente formato:

– numero n_i di archi uscenti da i;

– lista di n_i nodi destinazione, rappresentati con i numeri [0, n).

L’output contiene una riga contenente 1 se il grafo `e bipartito, 0 altrimenti.

Esempio

Input

5 (numero di elementi)

2 1 3 3 0 2 4 2 1 3 3 0 2 4 2 1 3

Output 1

1

Esempio:

6 1 5 3 0 3 4 0

2 4 5 1 2 1 0

0 3 4

5

4 5

E

Lettura grafo da input

1 3

2 0 /

Negli esercizi sarà richiesto di leggere un file avente il seguente formato:

Grafo bipartito

Esercizio

Scrivere un programma che legga da tastiera un grafo indiretto e stampi 1 se il grafo `e bipartito, 0 altrimenti. Il grafo `e rappresentato nel seguente formato: la prima riga contiene il numero n di nodi, le successive n righe contengono, per ciascun nodo i, con 0 i < n, il numero ni di archi uscenti da i seguito da una lista di ni nodi destinazione, rappresentati con i numeri [0, n). Si assuma che l’input contenga un grafo indiretto, e quindi che per ciascun arco da i a j esista anche l’arco da j ad i.

Un grafo bipartito `e un grafo tale che l’insieme dei suoi vertici si pu`o partizionare in due sottoinsiemi in cui ogni vertice `e collegato solo a vertici appartenenti alla partizione opposta.

Suggerimento: un grafo `e bipartito se e solo se `e possibile colorarlo usan- do due colori. Colorare il grafo corrisponde ad assegnare a ciascun vertice un colore diverso da quello dei suoi vertici adiacenti.

L’input `e costituito da:

• una riga contenente il numero n di nodi del grafo;

• n righe, una per ciasun nodo i, con i 2 [0, n), nel seguente formato:

– numero n_i di archi uscenti da i;

– lista di n_i nodi destinazione, rappresentati con i numeri [0, n).

L’output contiene una riga contenente 1 se il grafo `e bipartito, 0 altrimenti.

Esempio

Input

5 (numero di elementi)

2 1 3 3 0 2 4 2 1 3 3 0 2 4 2 1 3

Output 1

1

Esempio:

6 1 5 3 0 3 4 0

2 4 5 1 2 1 0

0 3 4

5

4 5

E

Lettura grafo da input

1 3

2 1 0 /

Negli esercizi sarà richiesto di leggere un file avente il seguente formato:

Grafo bipartito

Esercizio

Scrivere un programma che legga da tastiera un grafo indiretto e stampi 1 se il grafo `e bipartito, 0 altrimenti. Il grafo `e rappresentato nel seguente formato: la prima riga contiene il numero n di nodi, le successive n righe contengono, per ciascun nodo i, con 0 i < n, il numero ni di archi uscenti da i seguito da una lista di ni nodi destinazione, rappresentati con i numeri [0, n). Si assuma che l’input contenga un grafo indiretto, e quindi che per ciascun arco da i a j esista anche l’arco da j ad i.

Un grafo bipartito `e un grafo tale che l’insieme dei suoi vertici si pu`o partizionare in due sottoinsiemi in cui ogni vertice `e collegato solo a vertici appartenenti alla partizione opposta.

Suggerimento: un grafo `e bipartito se e solo se `e possibile colorarlo usan- do due colori. Colorare il grafo corrisponde ad assegnare a ciascun vertice un colore diverso da quello dei suoi vertici adiacenti.

L’input `e costituito da:

• una riga contenente il numero n di nodi del grafo;

• n righe, una per ciasun nodo i, con i 2 [0, n), nel seguente formato:

– numero n_i di archi uscenti da i;

– lista di n_i nodi destinazione, rappresentati con i numeri [0, n).

L’output contiene una riga contenente 1 se il grafo `e bipartito, 0 altrimenti.

Esempio

Input

5 (numero di elementi)

2 1 3 3 0 2 4 2 1 3 3 0 2 4 2 1 3

Output 1

1

Esempio:

6 1 5 3 0 3 4 0

2 4 5 1 2 1 0

0 3 4

5

4 5

E

Lettura grafo da input

1 3

2 1 0 /

Negli esercizi sarà richiesto di leggere un file avente il seguente formato:

Grafo bipartito

Esercizio

Scrivere un programma che legga da tastiera un grafo indiretto e stampi 1 se il grafo `e bipartito, 0 altrimenti. Il grafo `e rappresentato nel seguente formato: la prima riga contiene il numero n di nodi, le successive n righe contengono, per ciascun nodo i, con 0 i < n, il numero ni di archi uscenti da i seguito da una lista di ni nodi destinazione, rappresentati con i numeri [0, n). Si assuma che l’input contenga un grafo indiretto, e quindi che per ciascun arco da i a j esista anche l’arco da j ad i.

Un grafo bipartito `e un grafo tale che l’insieme dei suoi vertici si pu`o partizionare in due sottoinsiemi in cui ogni vertice `e collegato solo a vertici appartenenti alla partizione opposta.

Suggerimento: un grafo `e bipartito se e solo se `e possibile colorarlo usan- do due colori. Colorare il grafo corrisponde ad assegnare a ciascun vertice un colore diverso da quello dei suoi vertici adiacenti.

L’input `e costituito da:

• una riga contenente il numero n di nodi del grafo;

• n righe, una per ciasun nodo i, con i 2 [0, n), nel seguente formato:

– numero n_i di archi uscenti da i;

– lista di n_i nodi destinazione, rappresentati con i numeri [0, n).

L’output contiene una riga contenente 1 se il grafo `e bipartito, 0 altrimenti.

Esempio

Input

5 (numero di elementi)

2 1 3 3 0 2 4 2 1 3 3 0 2 4 2 1 3

Output 1

1

Esempio:

6 1 5 3 0 3 4 0

2 4 5 1 2 1 0

0 3 4

5

4 5

2

E

Lettura grafo da input

1 3

2 1 0 /

Negli esercizi sarà richiesto di leggere un file avente il seguente formato:

Grafo bipartito

Esercizio

Scrivere un programma che legga da tastiera un grafo indiretto e stampi 1 se il grafo `e bipartito, 0 altrimenti. Il grafo `e rappresentato nel seguente formato: la prima riga contiene il numero n di nodi, le successive n righe contengono, per ciascun nodo i, con 0 i < n, il numero ni di archi uscenti da i seguito da una lista di ni nodi destinazione, rappresentati con i numeri [0, n). Si assuma che l’input contenga un grafo indiretto, e quindi che per ciascun arco da i a j esista anche l’arco da j ad i.

Un grafo bipartito `e un grafo tale che l’insieme dei suoi vertici si pu`o partizionare in due sottoinsiemi in cui ogni vertice `e collegato solo a vertici appartenenti alla partizione opposta.

Suggerimento: un grafo `e bipartito se e solo se `e possibile colorarlo usan- do due colori. Colorare il grafo corrisponde ad assegnare a ciascun vertice un colore diverso da quello dei suoi vertici adiacenti.

L’input `e costituito da:

• una riga contenente il numero n di nodi del grafo;

• n righe, una per ciasun nodo i, con i 2 [0, n), nel seguente formato:

– numero n_i di archi uscenti da i;

– lista di n_i nodi destinazione, rappresentati con i numeri [0, n).

L’output contiene una riga contenente 1 se il grafo `e bipartito, 0 altrimenti.

Esempio

Input

5 (numero di elementi)

2 1 3 3 0 2 4 2 1 3 3 0 2 4 2 1 3

Output 1

1

Esempio:

6 1 5 3 0 3 4 0

2 4 5 1 2 1 0

0 3 4

5

4 5

2

E

Lettura grafo da input

1 3

2 1 0 /

1

Negli esercizi sarà richiesto di leggere un file avente il seguente formato:

Grafo bipartito

Esercizio

Scrivere un programma che legga da tastiera un grafo indiretto e stampi 1 se il grafo `e bipartito, 0 altrimenti. Il grafo `e rappresentato nel seguente formato: la prima riga contiene il numero n di nodi, le successive n righe contengono, per ciascun nodo i, con 0 i < n, il numero ni di archi uscenti da i seguito da una lista di ni nodi destinazione, rappresentati con i numeri [0, n). Si assuma che l’input contenga un grafo indiretto, e quindi che per ciascun arco da i a j esista anche l’arco da j ad i.

Un grafo bipartito `e un grafo tale che l’insieme dei suoi vertici si pu`o partizionare in due sottoinsiemi in cui ogni vertice `e collegato solo a vertici appartenenti alla partizione opposta.

Suggerimento: un grafo `e bipartito se e solo se `e possibile colorarlo usan- do due colori. Colorare il grafo corrisponde ad assegnare a ciascun vertice un colore diverso da quello dei suoi vertici adiacenti.

L’input `e costituito da:

• una riga contenente il numero n di nodi del grafo;

• n righe, una per ciasun nodo i, con i 2 [0, n), nel seguente formato:

– numero n_i di archi uscenti da i;

– lista di n_i nodi destinazione, rappresentati con i numeri [0, n).

L’output contiene una riga contenente 1 se il grafo `e bipartito, 0 altrimenti.

Esempio

Input

5 (numero di elementi)

2 1 3 3 0 2 4 2 1 3 3 0 2 4 2 1 3

Output 1

1

Esempio:

6 1 5 3 0 3 4 0

2 4 5 1 2 1 0

0 3 4

5

4 5

2

E

Lettura grafo da input

1 3

2 1 0 /

1

Negli esercizi sarà richiesto di leggere un file avente il seguente formato:

Grafo bipartito

Esercizio

Scrivere un programma che legga da tastiera un grafo indiretto e stampi 1 se il grafo `e bipartito, 0 altrimenti. Il grafo `e rappresentato nel seguente formato: la prima riga contiene il numero n di nodi, le successive n righe contengono, per ciascun nodo i, con 0 i < n, il numero ni di archi uscenti da i seguito da una lista di ni nodi destinazione, rappresentati con i numeri [0, n). Si assuma che l’input contenga un grafo indiretto, e quindi che per ciascun arco da i a j esista anche l’arco da j ad i.

Un grafo bipartito `e un grafo tale che l’insieme dei suoi vertici si pu`o partizionare in due sottoinsiemi in cui ogni vertice `e collegato solo a vertici appartenenti alla partizione opposta.

Suggerimento: un grafo `e bipartito se e solo se `e possibile colorarlo usan- do due colori. Colorare il grafo corrisponde ad assegnare a ciascun vertice un colore diverso da quello dei suoi vertici adiacenti.

L’input `e costituito da:

• una riga contenente il numero n di nodi del grafo;

• n righe, una per ciasun nodo i, con i 2 [0, n), nel seguente formato:

– numero n_i di archi uscenti da i;

– lista di n_i nodi destinazione, rappresentati con i numeri [0, n).

L’output contiene una riga contenente 1 se il grafo `e bipartito, 0 altrimenti.

Esempio

Input

5 (numero di elementi)

2 1 3 3 0 2 4 2 1 3 3 0 2 4 2 1 3

Output 1

1

Esempio:

6 1 5 3 0 3 4 0

2 4 5 1 2 1 0

0 3 4

5

4 5

2

0

E

Lettura grafo da input

1 3

2 1 0 /

1

Negli esercizi sarà richiesto di leggere un file avente il seguente formato:

Grafo bipartito

Esercizio

Scrivere un programma che legga da tastiera un grafo indiretto e stampi 1 se il grafo `e bipartito, 0 altrimenti. Il grafo `e rappresentato nel seguente formato: la prima riga contiene il numero n di nodi, le successive n righe contengono, per ciascun nodo i, con 0 i < n, il numero ni di archi uscenti da i seguito da una lista di ni nodi destinazione, rappresentati con i numeri [0, n). Si assuma che l’input contenga un grafo indiretto, e quindi che per ciascun arco da i a j esista anche l’arco da j ad i.

Un grafo bipartito `e un grafo tale che l’insieme dei suoi vertici si pu`o partizionare in due sottoinsiemi in cui ogni vertice `e collegato solo a vertici appartenenti alla partizione opposta.

Suggerimento: un grafo `e bipartito se e solo se `e possibile colorarlo usan- do due colori. Colorare il grafo corrisponde ad assegnare a ciascun vertice un colore diverso da quello dei suoi vertici adiacenti.

L’input `e costituito da:

• una riga contenente il numero n di nodi del grafo;

• n righe, una per ciasun nodo i, con i 2 [0, n), nel seguente formato:

– numero n_i di archi uscenti da i;

– lista di n_i nodi destinazione, rappresentati con i numeri [0, n).

L’output contiene una riga contenente 1 se il grafo `e bipartito, 0 altrimenti.

Esempio

Input

5 (numero di elementi)

2 1 3 3 0 2 4 2 1 3 3 0 2 4 2 1 3

Output 1

1

Esempio:

6 1 5 3 0 3 4 0

2 4 5 1 2 1 0

0 3 4

5

4 5

2 0

edges * read_graph() { edges * E;

int n, ne, i, j;

scanf(“%d”, &n);

E = (edges *) malloc(sizeof(edges) * n);

for (i=0; i < n; ++i) { scanf(“%d”, &(ne));

E[i].num_edges = ne;

E[i].edges = (int *) malloc(sizeof(int) * ne);

for (j=0; j < ne; ++j) {

scanf(“%d”, E[i].edges + j);

} }

return E;

}

Visita in profondità

0

1 2

3

4

5 3

Visita in profondità

0

1 2

3

4

5 3

4

Visita in profondità

0

1 2

3

4

5 3

4

2

Visita in profondità

0

1 2

3

4

5 3

4

2

5

Visita in profondità

0

1 2

3

4

5 3

4

2

5

0

Visita in profondità

0

1 2

3

4

5 3

4

2

5

0

void recursive_dfs(

edges *E, int src, int *colors ) {

int dest;

for (int i=0; i < E[src].num_edges; ++i) { dest = E[src].edges[i];

if (!colors[dest]) { colors[dest] = 1;

recursive_dfs(dest, E, colors);

} } }

int * dfs(edges *E, int n, int from) {

int * colors = (int *) malloc(sizeof(int)*n);

// inizializzo i colori

for (int i=0; i < n; ++i) colors[i] = 0;

colors[from] = 1;

// chiamata ricorsiva

recursive_dfs(E, from, colors);

return colors;

}

Visita in profondità

0

1 2

3

4

5 3

4

2

5

0

void recursive_dfs(

edges *E, int src, int *colors ) {

int dest;

for (int i=0; i < E[src].num_edges; ++i) { dest = E[src].edges[i];

if (!colors[dest]) { colors[dest] = 1;

recursive_dfs(dest, E, colors);

} } }

int * dfs(edges *E, int n, int from) {

int * colors = (int *) malloc(sizeof(int)*n);

// inizializzo i colori

for (int i=0; i < n; ++i) colors[i] = 0;

colors[from] = 1;

// chiamata ricorsiva

recursive_dfs(E, from, colors);

return colors;

} int * dfs(edges *E, int n, int from) {

int * colors = (int *) malloc(sizeof(int) * n);

int * stack = (int *) malloc(sizeof(int) * n);

int stack_size, src, dest, i;

// inizializzo i colori

for (i=0; i < n; ++i) colors[i] = 0;

colors[from] = 1;

// inizializzo lo stack

stack[0] = from; stack_size = 1;

// loop fino a terminazione dello stack while (stack_size) {

src = stack[--stack_size];

for (i=0; i < E[src].num_edges; ++i) { dest = E[src].edges[i];

if (!colors[dest]) { colors[dest] = 1;

stack[stack_size++] = dest;

} } }

// libero la memoria free(stack);

return colors;

}

Visita in ampiezza

0

1 2

3

4

5 3

Visita in ampiezza

0

1 2

3

4

5 3

4

Visita in ampiezza

0

1 2

3

4

5 3

4

5

Visita in ampiezza

0

1 2

3

4

5 3

4

2

5

Visita in ampiezza

0

1 2

3

4

5 3

4

2

5

0

Visita in ampiezza

0

1 2

3

4

5 3

4

2

5

0

typedef struct _queue { int * values;

int capacity;

int head;

int tail;

} queue;

void queue_init(queue * q, int capacity);

void queue_deinit(queue * q);

void queue_pushBack(queue * q, int value);

int queue_popFront(queue * q);

int queue_isEmpty(queue * q);

Visita in ampiezza

0

1 2

3

4

5 3

4

2

5

0

typedef struct _queue { int * values;

int capacity;

int head;

int tail;

} queue;

void queue_init(queue * q, int capacity);

void queue_deinit(queue * q);

void queue_pushBack(queue * q, int value);

int queue_popFront(queue * q);

int queue_isEmpty(queue * q);

int * bfs(edges *E, int n, int from) {

int * colors = (int *) malloc(sizeof(int) * n);

queue q;

int src, dest, i;

// inizializzo i colori

for (i=0; i < n; ++i) colors[i] = 0;

colors[from] = 1;

// inizializzo la coda queue_init(&q, n);

queue_pushBack(&q, from);

// loop fino a terminazione della coda while (!queue_isEmpty(&q)) {

src = queue_popFront(&q);

for (i=0; i < E[src].num_edges; ++i) { dest = E[src].edges[i];

if (!colors[dest]) { colors[dest] = 1;

queue_pushBack(&q, dest);

} } }

// libero la memoria queue_deinit(&q);

return colors;

}

Visita in ampiezza

0

1 2

3

4

5 3

4

2

5

0

typedef struct _queue { int * values;

int capacity;

int head;

int tail;

} queue;

void queue_init(queue * q, int capacity);

void queue_deinit(queue * q);

void queue_pushBack(queue * q, int value);

int queue_popFront(queue * q);

int queue_isEmpty(queue * q);

int * bfs(edges *E, int n, int from) {

int * colors = (int *) malloc(sizeof(int) * n);

queue q;

int src, dest, i;

// inizializzo i colori

for (i=0; i < n; ++i) colors[i] = 0;

colors[from] = 1;

// inizializzo la coda queue_init(&q, n);

queue_pushBack(&q, from);

// loop fino a terminazione della coda while (!queue_isEmpty(&q)) {

src = queue_popFront(&q);

for (i=0; i < E[src].num_edges; ++i) { dest = E[src].edges[i];

if (!colors[dest]) { colors[dest] = 1;

queue_pushBack(&q, dest);

} } }

// libero la memoria queue_deinit(&q);

return colors;

}

Da implementare…

Esercizio 1

Grafo bipartito

Grafo bipartito

Esercizio

Scrivere un programma che legga da tastiera un grafo indiretto e stampi 1 se il grafo `e bipartito, 0 altrimenti. Il grafo `e rappresentato nel seguente formato: la prima riga contiene il numero n di nodi, le successive n righe contengono, per ciascun nodo i, con 0  i < n, il numero n i di archi uscenti da i seguito da una lista di n _i nodi destinazione, rappresentati con i numeri [0, n). Si assuma che l’input contenga un grafo indiretto, e quindi che per ciascun arco da i a j esista anche l’arco da j ad i.

Un grafo bipartito `e un grafo tale che l’insieme dei suoi vertici si pu`o partizionare in due sottoinsiemi in cui ogni vertice `e collegato solo a vertici appartenenti alla partizione opposta.

Suggerimento: un grafo `e bipartito se e solo se `e possibile colorarlo usan- do due colori. Colorare il grafo corrisponde ad assegnare a ciascun vertice un colore diverso da quello dei suoi vertici adiacenti.

L’input `e costituito da:

• una riga contenente il numero n di nodi del grafo;

• n righe, una per ciasun nodo i, con i 2 [0, n), nel seguente formato:

– numero n _i di archi uscenti da i;

– lista di n _i nodi destinazione, rappresentati con i numeri [0, n).

L’output contiene una riga contenente 1 se il grafo `e bipartito, 0 altrimenti.

Esempio

Input

5 (numero di elementi)

2 1 3 3 0 2 4 2 1 3 3 0 2 4 2 1 3

Output 1

1

Esercizio 2

Grafo connesso

Grafo connesso

Esercizio

Scrivere un programma che legga da tastiera un grafo indiretto e stampi 1 se il grafo `e connesso, 0 altrimenti. Il grafo `e rappresentato nel seguente formato: la prima riga contiene il numero n di nodi, le successive n righe contengono, per ciascun nodo i, con 0  i < n, il numero n ⁱ di archi uscenti da i seguito da una lista di n _i nodi destinazione, rappresentati con i numeri [0, n). Si assuma che l’input contenga un grafo indiretto, e quindi che per ciascun arco da i a j esiste anche l’arco da j ad i.

Un grafo `e connesso quando esiste un percorso tra due vertici qualunque del grafo. Il programma deve eseguire una visita DFS (a partire da un nodo qualunque, perch´e?) del grafo per stabilire se questo `e connesso.

L’input `e costituito da:

• una riga contenente il numero n di nodi del grafo;

• n righe, una per ciasun nodo i, con i 2 [0, n), nel seguente formato:

– numero n _i di archi uscenti da i;

– lista di n _i nodi destinazione, rappresentati con i numeri [0, n).

L’output contiene una riga contenente 1 se il grafo `e connesso, -0 altrimenti.

1

Esercizio 3

Percorso minimo

Percorso minimo

Esercizio

Scrivere un programma che legga da tastiera un grafo diretto, una sequenza di m query composte da due indici ciascuna e stampi, per ciascuna query, la lunghezza del percorso minimo che collega i rispettivi due nodi della query. Il grafo `e rappresentato nel seguente formato: la prima riga contiene il numero n di nodi, le successive n righe contengono, per ciascun nodo i, con 0  i < n, il numero n ⁱ di archi uscenti da i seguito da una lista di n _i nodi destinazione, rappresentati con i numeri [0, n).

Il percorso minimo dal nodo i al nodo j `e il percorso che porta da i a j avente il minor numero di nodi. A tale scopo si esegua una visita BFS del grafo a partire dal nodo i per stabilire il percorso minimo che porta al nodo j, qualora questo esista.

L’input `e costituito da:

• una riga contenente il numero n di nodi del grafo;

• n righe, una per ciasun nodo i, con i 2 [0, n), nel seguente formato:

– numero n i di archi uscenti da i;

– lista di n i nodi destinazione, rappresentati con i numeri [0, n).

• una riga contenente il numero m di query;

• m righe, una per ciasuna query, contenenti l’indice del nodo di partenza e l’indice del nodo di destinazione.

L’output contiene m righe contenenti ciascuna la lunghezza del percorso minimo che collega i due nodi della rispettiva query e -1 quando i nodi non sono collegati.

1

Esercizio 4

Diametro grafo

Diametro grafo

Esercizio

Scrivere un programma che legga da tastiera un grafo diretto e stampi il diametro del grafo. Il grafo `e rappresentato nel seguente formato: la prima riga contiene il numero n di nodi, le successive n righe contengono, per ciascun nodo i, con 0  i < n, il numero n ⁱ di archi uscenti da i seguito da una lista di n _i nodi destinazione, rappresentati con i numeri [0, n).

Il diametro di un grafo `e la lunghezza del “pi` u lungo cammino minimo”

fra tutte le coppie di nodi. Il programma deve eseguire una visita BFS a partire da ciascun nodo i del grafo per stabilire il cammino minimo pi` u lungo a partire da i, e quindi stampare il massimo tra tutti questi.

L’input `e costituito da:

• una riga contenente il numero n di nodi del grafo;

• n righe, una per ciasun nodo i, con i 2 [0, n), nel seguente formato:

– numero n _i di archi uscenti da i;

– lista di n _i nodi destinazione, rappresentati con i numeri [0, n).

L’output contiene una sola riga contenente il diametro del grafo.

Esempio

Input

6 (numero di elementi)

2 1 3 2 0 2 2 1 5 2 0 4 1 2 1 2

Output 1

1

Puzzle

Puzzle

Formiche in riga

Una colonia di n formiche `e disposta in linea retta su una corda lunga esat- tamente n segmenti. Le formiche possono muoversi solo in orizzontale, in entrambi i versi, ma non possono passare una sopra l’altra. Le formiche una volta decisa una direzione non la cambiano pi` u fino a che non si scontrano con un’altra formica che andava in direzione opposta. Le formiche si muo- vono tutte insieme a step regolari, di un segmento alla volta nelle rispettive direzioni. Quando due formiche si scontrano cambiano direzione e tornano al segmento che occupavano (ma questa volta andando in direzione oppo- sta). Quando una formica fa un passo oltre il primo o l’ultimo dei segmenti cade dalla corda.

Inizialmente ogni formica occupa un segmento distinto della corda, ma con una direzione iniziale a noi sconosciuta. Individuare il numero di step necessari affinch´e al caso pessimo tutte le formiche cadano dalla corda.

1