#include <stdio.h>
#include <stdlib.h>
// Estructura de un nodo del grafo
struct Node {
int vertex; // Número del vértice
struct Node* next; // Puntero al siguiente nodo en la lista de adyacencia
} ;
// Definición de la estructura del grafo
struct Graph {
int numVertices; // Número de vértices en el grafo
struct Node** adjLists; // Lista de adyacencia para cada vértice
} ;
// Función para crear un nuevo nodo en el grafo
struct Node* createNode( int v) {
struct Node
* newNode
= ( struct Node
* ) malloc ( sizeof ( struct Node
) ) ; newNode-> vertex = v;
newNode-> next = NULL;
return newNode;
}
// Función para crear un grafo con un número dado de vértices
struct Graph* createGraph( int vertices) {
struct Graph
* graph
= ( struct Graph
* ) malloc ( sizeof ( struct Graph
) ) ; graph-> numVertices = vertices;
// Asignación de memoria para la lista de adyacencia
graph
-> adjLists
= ( struct Node
** ) malloc ( vertices
* sizeof ( struct Node
* ) ) ;
// Inicialización de cada lista de adyacencia como vacía
for ( int i = 0 ; i < vertices; i++ ) {
graph-> adjLists[ i] = NULL;
}
return graph;
}
// Función para agregar una arista al grafo no dirigido
void addEdge( struct Graph* graph, int src, int dest) {
// Agregar la arista de src a dest
struct Node* newNode = createNode( dest) ;
newNode-> next = graph-> adjLists[ src] ;
graph-> adjLists[ src] = newNode;
// Debe agregar una arista de dest a src pues no es un grafo dirigido
newNode = createNode( src) ;
newNode-> next = graph-> adjLists[ dest] ;
graph-> adjLists[ dest] = newNode;
}
// Función para imprimir el grafo
void printGraph( struct Graph* graph) {
for ( int i = 0 ; i < graph-> numVertices; i++ ) {
struct Node* temp = graph-> adjLists[ i] ;
printf ( "Lista de adyacencia del vértice %d\n " , i
) ; while ( temp) {
printf ( " -> %d" , temp
-> vertex
) ; temp = temp-> next;
}
}
}
int main( ) {
int numVertices = 5 ;
struct Graph* graph = createGraph( numVertices) ;
addEdge( graph, 0 , 1 ) ;
addEdge( graph, 0 , 4 ) ;
addEdge( graph, 1 , 2 ) ;
addEdge( graph, 1 , 3 ) ;
addEdge( graph, 1 , 4 ) ;
addEdge( graph, 2 , 3 ) ;
addEdge( graph, 3 , 4 ) ;
printGraph( graph) ;
return 0 ;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KCi8vIEVzdHJ1Y3R1cmEgZGUgdW4gbm9kbyBkZWwgZ3JhZm8Kc3RydWN0IE5vZGUgewogICAgaW50IHZlcnRleDsgICAgICAgICAgICAgLy8gTsO6bWVybyBkZWwgdsOpcnRpY2UKICAgIHN0cnVjdCBOb2RlKiBuZXh0OyAgICAgIC8vIFB1bnRlcm8gYWwgc2lndWllbnRlIG5vZG8gZW4gbGEgbGlzdGEgZGUgYWR5YWNlbmNpYQp9OwoKLy8gRGVmaW5pY2nDs24gZGUgbGEgZXN0cnVjdHVyYSBkZWwgZ3JhZm8Kc3RydWN0IEdyYXBoIHsKICAgIGludCBudW1WZXJ0aWNlczsgICAgICAgIC8vIE7Dum1lcm8gZGUgdsOpcnRpY2VzIGVuIGVsIGdyYWZvCiAgICBzdHJ1Y3QgTm9kZSoqIGFkakxpc3RzOyAvLyBMaXN0YSBkZSBhZHlhY2VuY2lhIHBhcmEgY2FkYSB2w6lydGljZQp9OwoKLy8gRnVuY2nDs24gcGFyYSBjcmVhciB1biBudWV2byBub2RvIGVuIGVsIGdyYWZvCnN0cnVjdCBOb2RlKiBjcmVhdGVOb2RlKGludCB2KSB7CiAgICBzdHJ1Y3QgTm9kZSogbmV3Tm9kZSA9IChzdHJ1Y3QgTm9kZSopbWFsbG9jKHNpemVvZihzdHJ1Y3QgTm9kZSkpOwogICAgbmV3Tm9kZS0+dmVydGV4ID0gdjsKICAgIG5ld05vZGUtPm5leHQgPSBOVUxMOwogICAgcmV0dXJuIG5ld05vZGU7Cn0KCi8vIEZ1bmNpw7NuIHBhcmEgY3JlYXIgdW4gZ3JhZm8gY29uIHVuIG7Dum1lcm8gZGFkbyBkZSB2w6lydGljZXMKc3RydWN0IEdyYXBoKiBjcmVhdGVHcmFwaChpbnQgdmVydGljZXMpIHsKICAgIHN0cnVjdCBHcmFwaCogZ3JhcGggPSAoc3RydWN0IEdyYXBoKiltYWxsb2Moc2l6ZW9mKHN0cnVjdCBHcmFwaCkpOwogICAgZ3JhcGgtPm51bVZlcnRpY2VzID0gdmVydGljZXM7CgogICAgLy8gQXNpZ25hY2nDs24gZGUgbWVtb3JpYSBwYXJhIGxhIGxpc3RhIGRlIGFkeWFjZW5jaWEKICAgIGdyYXBoLT5hZGpMaXN0cyA9IChzdHJ1Y3QgTm9kZSoqKW1hbGxvYyh2ZXJ0aWNlcyAqIHNpemVvZihzdHJ1Y3QgTm9kZSopKTsKCiAgICAvLyBJbmljaWFsaXphY2nDs24gZGUgY2FkYSBsaXN0YSBkZSBhZHlhY2VuY2lhIGNvbW8gdmFjw61hCiAgICBmb3IgKGludCBpID0gMDsgaSA8IHZlcnRpY2VzOyBpKyspIHsKICAgICAgICBncmFwaC0+YWRqTGlzdHNbaV0gPSBOVUxMOwogICAgfQoKICAgIHJldHVybiBncmFwaDsKfQoKLy8gRnVuY2nDs24gcGFyYSBhZ3JlZ2FyIHVuYSBhcmlzdGEgYWwgZ3JhZm8gbm8gZGlyaWdpZG8Kdm9pZCBhZGRFZGdlKHN0cnVjdCBHcmFwaCogZ3JhcGgsIGludCBzcmMsIGludCBkZXN0KSB7CiAgICAvLyBBZ3JlZ2FyIGxhIGFyaXN0YSBkZSBzcmMgYSBkZXN0CiAgICBzdHJ1Y3QgTm9kZSogbmV3Tm9kZSA9IGNyZWF0ZU5vZGUoZGVzdCk7CiAgICBuZXdOb2RlLT5uZXh0ID0gZ3JhcGgtPmFkakxpc3RzW3NyY107CiAgICBncmFwaC0+YWRqTGlzdHNbc3JjXSA9IG5ld05vZGU7CgogICAgLy8gRGViZSBhZ3JlZ2FyIHVuYSBhcmlzdGEgZGUgZGVzdCBhIHNyYyBwdWVzIG5vIGVzIHVuIGdyYWZvIGRpcmlnaWRvCiAgICBuZXdOb2RlID0gY3JlYXRlTm9kZShzcmMpOwogICAgbmV3Tm9kZS0+bmV4dCA9IGdyYXBoLT5hZGpMaXN0c1tkZXN0XTsKICAgIGdyYXBoLT5hZGpMaXN0c1tkZXN0XSA9IG5ld05vZGU7Cn0KCi8vIEZ1bmNpw7NuIHBhcmEgaW1wcmltaXIgZWwgZ3JhZm8Kdm9pZCBwcmludEdyYXBoKHN0cnVjdCBHcmFwaCogZ3JhcGgpIHsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgZ3JhcGgtPm51bVZlcnRpY2VzOyBpKyspIHsKICAgICAgICBzdHJ1Y3QgTm9kZSogdGVtcCA9IGdyYXBoLT5hZGpMaXN0c1tpXTsKICAgICAgICBwcmludGYoIkxpc3RhIGRlIGFkeWFjZW5jaWEgZGVsIHbDqXJ0aWNlICVkXG4iLCBpKTsKICAgICAgICB3aGlsZSAodGVtcCkgewogICAgICAgICAgICBwcmludGYoIiAtPiAlZCIsIHRlbXAtPnZlcnRleCk7CiAgICAgICAgICAgIHRlbXAgPSB0ZW1wLT5uZXh0OwogICAgICAgIH0KICAgICAgICBwcmludGYoIlxuIik7CiAgICB9Cn0KCmludCBtYWluKCkgewogICAgaW50IG51bVZlcnRpY2VzID0gNTsKICAgIHN0cnVjdCBHcmFwaCogZ3JhcGggPSBjcmVhdGVHcmFwaChudW1WZXJ0aWNlcyk7CgogICAgYWRkRWRnZShncmFwaCwgMCwgMSk7CiAgICBhZGRFZGdlKGdyYXBoLCAwLCA0KTsKICAgIGFkZEVkZ2UoZ3JhcGgsIDEsIDIpOwogICAgYWRkRWRnZShncmFwaCwgMSwgMyk7CiAgICBhZGRFZGdlKGdyYXBoLCAxLCA0KTsKICAgIGFkZEVkZ2UoZ3JhcGgsIDIsIDMpOwogICAgYWRkRWRnZShncmFwaCwgMywgNCk7CgogICAgcHJpbnRHcmFwaChncmFwaCk7CgogICAgcmV0dXJuIDA7Cn0K