/* programma per costruire una partizione del grafo in foreste disgiunte */
#include <stdio.h>
#include <stdlib.h>
/********************/
/* definizione tipi */
/********************/
/* implementazione di insiemi disgiunti con liste */
typedef struct lnode {
int id;
struct lnode* next;
struct lnode* rap;
} lnode;
/* implementazione di insiemi disgiunti con foreste */
typedef struct fnode {
int id;
struct fnode* parent;
} fnode;
/* costruzione dell'albero di visita per la ricerca di un ciclo */
typedef struct tnode { int id;
struct tnode* parent;
struct tnode** sons;
int numsons;
} tnode;
/*********************/
/* variabili globali */
/*********************/
/* matrice di adiacenza per la rappresentazione del grafo */
short **AdjMatrix;
/* array che implementa la collezione di insiemi disgiunti (liste) */
lnode **ListColl;
/* array che implementa la collezione di insiemi disgiunti (foreste) */
fnode **ForestColl;
/* array che memorizza i puntatori alle strutture lnode */
lnode **LNodes;
/* array che memorizza i puntatori alle strutture fnode */
fnode **FNodes;
/* array per la visita in ampiezza del grafo */
tnode **Queue;
/* numero di nodi del grafo */
int NumNodes;
/* numero di archi del grafo */
int NumEdges;
/* estremi di un arco da eliminare */
int Extr1, Extr2;
/* rappresentazione del grafo [1=liste, 2=foreste] */
char GraphRapType;
/*********************/
/* funzioni */
/*********************/
/* legge il grafo in input come matrice di adiacenza */
void ReadGraph() {
/* identifichiamo i nodi con interi da 0 a NumNodes-1 */
/* legge il numero di nodi del grafo */
printf("\n numero di nodi: ");
scanf("%d, &NumNodes");
/* alloca memoria e inizializza la matrice di adiacenza */
AdjMatrix = (short**)malloc(NumNodes * sizeof(short*));
for (int i=0; i<NumNodes; i++)
AdjMatrix[i] = (short*)malloc(NumNodes * sizeof(short));
for (i=0; i<NumNodes; i++)
for (int j=0; j<NumNodes; j++) AdjMatrix[i][j] = 0;
/* legge il tipo di rappresentazione per la collezione di insiemi disgiunti */
printf("\n rappresentazione degli insiemi disgiunti [1=liste, 2=foreste]: ");
do
scanf("%d", &GraphRapType);
while ((GraphRapType != 1) && (GraphRapType != 2));
/* alloca memoria e inizializza la collezione */
if (GraphRapType == 1) {
ListColl = (lnode**)malloc(NumNodes * sizeof(lnode*));
for (i=0; i<NumNodes; i++) ListColl[i] = NULL;
LNodes = (lnode**)malloc(NumNodes * sizeof(lnode*));
} else {
ForestColl = (fnode**)malloc(NumNodes * sizeof(fnode*));
for (i=0; i<NumNodes; i++) ForestColl[i] = NULL;
FNodes = (fnode**)malloc(NumNodes * sizeof(fnode*));
}
/* legge gli archi del grafo */
printf("\n numero di archi: ");
scanf("%d, &NumEdges");
for (i=0; i<NumEdges; i++) {
int a, b;
printf("\n arco %d-esimo: ");
scanf("%d %d", &a, &b);
AdjMatrix[a][b] = 1;
AdjMatrix[a][b] = 1;
} }
/* stampa il risultato */
void PrintForests() {
/* stampa i nodi e gli archi del grafo risultante */
printf("\nForeste Disgiunte:");
printf("\nNodi:");
if (GraphRapType == 1)
for (int i=0; i<NumNodes; i++) {
if (ListColl[i] != NULL) {
lnode* pn = ListColl[i];
while (pn != NULL)
printf("%d ", pn->id);
printf("\n");
} } else {
for (int i=0; i<NumNodes; i++) {
printf("%d\n", ForestColl[i]->id);
fnode* pn = FNodes[i];
do {
printf("%d ", pn->id);
pn = pn->parent;
}
while (pn != pn->parent);
printf("\n");
} }
printf("\nArchi");
for(int i=0; i<NumNodes; i++) for(int j=0; j<i; j++) if (AdjMatrix[i][j]) printf("%d %d", i, j);
}
/* crea un insieme disgiunto con un solo elemento */
void MakeSet(short n) {
if (GraphRapType == 1) {
lnode* pn = (lnode*)malloc(sizeof(lnode));
pn->id = n;
pn->next = NULL;
pn->rap = pn;
ListColl[n] = pn;
LNodes[n] = pn;
} else {
fnode* pn = (fnode*)malloc(sizeof(fnode));
pn->id = n;
pn->parent = pn;
ForestColl[n] = pn;
FNodes[n] = pn;
} }
/* trova il rappresentante dell'insieme che contiene a (liste) */
lnode* LFindSet(int n) { return LNodes[n]->rap;
}
/* trova il rappresentante dell'insieme che contiene a (foreste) */
fnode* FFindSet(int n) {
fnode* pn = FNodes[n];
while (pn != pn->parent) pn = pn->parent;
return pn;
}
/* unisce gli insiemi disgiunti che contengono a e b */
void Union(int a, int b) { if (GraphRapType == 1) {
lnode* pn1, *pn2, *pn3;
pn1=(lnode*)LFindSet(a);
pn2=(lnode*)LFindSet(b);
if (pn1 != pn2) {
/* trova l'ultimo elemento dell'insieme che contiene b */
pn3 = pn2;
while (pn3->next != NULL) pn3 = pn3->next;
/* aggiorna tutti gli elementi dell'insieme che contiene a */
while (pn1 != NULL) {
pn1->rap = pn2;
pn1 = pn1->next;
}
ListColl[a] = NULL;
} } else {
fnode* pn1, *pn2;
pn1=(fnode*)FFindSet(a);
pn2=(fnode*)FFindSet(b);
if (pn1 != pn2) {
pn1->parent = pn2;
ForestColl[a] = NULL;
} } }
void ConnectedComponents() {
/* costruisce le componenti connesse del grafo */
for (int i=0; i<NumNodes; i++) MakeSet(i);
for (i=0; i<NumNodes; i++) for (int j=0; j<i; j++) if (AdjMatrix[i][j]) if (GraphRapType == 1) {
if (LFindSet(i) != LFindSet(j)) Union(i, j);
} else
if (FFindSet(i) != FFindSet(j)) Union(i, j);
}
/* libera memoria occupata dall'albero di visita */
void DestroyTree(tnode* t) {
for (int i=0; i<t->numsons; i++) DestroyTree(t->sons[i]);
free(t);
}
/* controlla la presenza di un ciclo */
char CheckCicle(int i)
{ /* individua la presenza di un ciclo nel sottografo in cui si trova i */
char found = 0;
while (!found) {
if (GraphRapType == 1) {
if (ListColl[i] != NULL) {
/* costruisci nodo radice per i */
tnode* troot = (tnode*)malloc(sizeof(tnode));
troot->sons = (tnode**)malloc(100*sizeof(tnode*));
troot->id = ListColl[i]->id;
troot->parent = NULL;
/* inizializza coda per la visita in ampiezza */
Queue = (tnode**)malloc(1000*sizeof(lnode*));
int head = 0, tail = 0;
Queue[++tail] = troot;
/* costruisci un figlio per ogni nodo adiacente e ripeti */
while (head <= tail) {
int curson = 0;
tnode* t = Queue[head];
for (int j=0; j<i; j++) {
if (AdjMatrix[t->id][j] && (j != t->parent->id)) {
/* inserisci il nuovo figlio nell'albero e nella coda */
tnode* tson = (tnode*)malloc(sizeof(tnode));
tson->sons = (tnode**)malloc(100*sizeof(tnode*));
tson->id = j;
tson->parent = t;
Queue[++tail] = tson;
t->sons[++curson] = tson;
/* controlla la presenza di cicli */
tnode* pt = t;
while (pt != NULL)
if (pt->id == tson->id) {
/* aggiorna il valore di Extr1 e Extr2 per l'eliminazione dell'a rco */
Extr1 = tson->parent->id;
Extr2 = pt->id;
DestroyTree(troot);
free(Queue);
return 0;
} }
} head++;
}
/* ciclo non trovato */
return 1;
} } else
if (ForestColl[i] != NULL) {
/* costruisci nodo radice per i */
tnode* troot = (tnode*)malloc(sizeof(tnode));
troot->sons = (tnode**)malloc(100*sizeof(tnode*));
troot->id = ForestColl[i]->id;
troot->parent = NULL;
/* inizializza coda per la visita in ampiezza */
Queue = (tnode**)malloc(1000*sizeof(lnode*));
int head = 0, tail = 0;
Queue[++tail] = troot;
/* costruisci un figlio per ogni nodo adiacente e ripeti */
while (head <= tail) {
tnode* t = Queue[head];
int curson = 0;
for (int j=0; j<i; j++) {
if (AdjMatrix[t->id][j] && (j != t->parent->id)) {
/* inserisci il nuovo figlio nell'albero e nella coda */
tnode* tson = (tnode*)malloc(sizeof(tnode));
tson->sons = (tnode**)malloc(100*sizeof(tnode*));
tson->id = j;
tson->parent = t;
Queue[++tail] = tson;
t->sons[++curson] = tson;
/* controlla la presenza di cicli */
tnode* pt = t;
while (pt != NULL)
if (pt->id == tson->id) {
/* aggiorna il valore di Extr1 e Extr2 per l'eliminazione dell'a rco */
Extr1 = tson->parent->id;
Extr2 = pt->id;
DestroyTree(troot);
free(Queue);
return 0;
} }
} head++;
}
/* ciclo non trovato */
return 1;
} }
}
/* main */
void main()
{ /* legge il grafo e inizalizza le strutture */
ReadGraph();
/* costruisce le componenti connesse del grafo */
ConnectedComponents();
/* elimina i cicli dal grafo */
char end=0;
while (!end) {
for(int i=0; i<NumNodes; i++) {
end = CheckCicle(i);
if (!end) {
/* elimina arco */
AdjMatrix[Extr1][Extr2] = 0;
AdjMatrix[Extr2][Extr1] = 0;
} } }
/* stampa risultato */
PrintForests();
}
