#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define DIM 100000
struct Persona
{
int valor;
int clase;
};
typedef struct Persona Persona;
struct NodoArbolPersona
{
Persona *persona;
struct NodoArbolPersona *menores, *mayores;
};
typedef struct NodoArbolPersona NodoArbolPersona;
void insertar(NodoArbolPersona **arbol, Persona *persona)
{
if(!(*arbol))
{
(*arbol
) = malloc(sizeof(NodoArbolPersona
)); (*arbol)->persona = persona;
(*arbol)->menores = NULL;
(*arbol)->mayores = NULL;
return;
}
if(persona->valor < (*arbol)->persona->valor)
insertar(&((*arbol)->menores), persona);
else
insertar(&((*arbol)->mayores), persona);
}
Persona* buscar(NodoArbolPersona *arbol, int valor)
{
if(!arbol)
return NULL;
if(arbol->persona->valor == valor)
return arbol->persona;
if(valor < arbol->persona->valor)
return buscar(arbol->menores, valor);
return buscar(arbol->mayores,valor);
}
void cambiar_clase(NodoArbolPersona *amigos, int nueva_clase)
{
if(!amigos)
return;
amigos->persona->clase = nueva_clase;
cambiar_clase(amigos->menores, nueva_clase);
cambiar_clase(amigos->mayores, nueva_clase);
}
void fusionar_arboles(NodoArbolPersona **destino, NodoArbolPersona *origen)
{
if(!(*destino))
*destino = origen;
if((*destino)->persona->valor == origen->persona->valor)
return;
if(origen->persona->valor < (*destino)->persona->valor)
fusionar_arboles(&((*destino)->menores),origen);
else
fusionar_arboles(&((*destino)->mayores),origen);
}
void insertar_amigos(NodoArbolPersona *amigos[DIM/2], NodoArbolPersona **personas, int a, int b)
{
Persona *persona1,*persona2, *aux;
int i,clase_aux;
if((persona1 = buscar(*personas,a)))
{
if((persona2 = buscar(*personas,b))) //ambas personas existen
{
if(persona1->clase != persona2->clase)
{
//pertenecen a distintas clases y hay que fusionarlas
if(persona1->clase > persona2->clase)
{
aux = persona2;
persona2 = persona1;
persona1 = aux;
}
clase_aux = persona2->clase;
cambiar_clase(amigos[persona2->clase],persona1->clase); //cambiamos toda la clase b para que apunte a a.
fusionar_arboles(&(amigos[persona1->clase]),amigos[clase_aux]); //añadimos toda el arbol b a a.
amigos[clase_aux] = NULL;
}
}
else //existe p1, pero no p2
{
persona2
= malloc(sizeof(Persona
));
persona2->valor = b;
persona2->clase = persona1->clase;
insertar(personas, persona2);
insertar(&(amigos[persona1->clase]), persona2);
}
}
else //persona1 no existe
{
if((persona2 = buscar(*personas,b)))
{
//existe p2 pero no p1
persona1
= malloc(sizeof(Persona
));
persona1->valor = a;
persona1->clase = persona2->clase;
insertar(personas, persona1);
insertar(&(amigos[persona2->clase]), persona1);
}
else //no existen ninguna de las dos personas
{
//buscamos la primera clase que este vacia
for(i = 0 ; amigos[i] ; i++);
//creamos las personas:
persona1
= malloc(sizeof(Persona
)); persona2
= malloc(sizeof(Persona
));
persona1->valor = a;
persona2->valor = b;
persona1->clase = persona2->clase = i;
insertar(personas,persona1);
insertar(personas,persona2);
insertar(&(amigos[i]),persona1);
insertar(&(amigos[i]),persona2);
}
}
return;
}
//tenemos dos funciones para liberar la memoria de los arboles
//la unica diferencia es que la primera libera el dato "persona"
//y la segunda no.
void destruir_personas(NodoArbolPersona **personas)
{
if(!(*personas))
return;
destruir_personas(&((*personas)->menores));
destruir_personas(&((*personas)->mayores));
free((*personas
)->persona
);
*personas = NULL;
}
void destruir_clase(NodoArbolPersona **amigos)
{
if(!(*amigos))
return;
destruir_personas(&((*amigos)->menores));
destruir_personas(&((*amigos)->mayores));
*amigos = NULL;
}
void problema_interactivo()
{
//cada componente del vector es un arbol que relaciona los amigos que forman una "clase"
NodoArbolPersona *clases[DIM / 2], *personas = NULL; //personas: arbol de elementos valor-clase
Persona *persona1, *persona2;
int num_personas, num_casos, amigo1, amigo2;
char operador;
for(num_personas = 0 ; num_personas < DIM / 2 ; num_personas++)
clases[num_personas] = NULL;
scanf("%d", &num_personas
);
while(num_casos--)
{
scanf("%c%d%d", &operador
, &amigo1
, &amigo2
);
switch(operador)
{
case 'S':
insertar_amigos(clases, &personas,amigo1, amigo2);
break;
case 'P':
if((persona1 = buscar(personas,amigo1)) && (persona2 = buscar(personas,amigo2)))
{
if(persona1->clase == persona2->clase)
else
}
else
}
}
destruir_personas(&personas);
for(num_personas = 0 ; num_personas < DIM / 2 ; num_personas++)
destruir_clase(&(clases[num_personas]));
}
void problema_aleatorio()
{
//cada componente del vector es un arbol que relaciona los amigos que forman una "clase"
NodoArbolPersona *clases[DIM / 2], *personas = NULL; //personas: arbol de elementos valor-clase
Persona *persona1, *persona2;
int num_personas, num_casos = DIM, amigo1, amigo2;
char operador;
char entrada[20];
for(num_personas = 0 ; num_personas < DIM / 2 ; num_personas++)
clases[num_personas] = NULL;
while(num_casos--)
{
//vamos a forzar a que, aproximadamente, el 60% de los casos sean saludos
sprintf(entrada
,"%c %d %d",rand() % 10 < 6 ? 'S' : 'P', rand() % (DIM
+ 1), rand() % (DIM
+ 1)); sscanf(entrada
,"%c%d%d", &operador
, &amigo1
, &amigo2
);
switch(operador)
{
case 'S':
insertar_amigos(clases, &personas,amigo1, amigo2);
break;
case 'P':
if((persona1 = buscar(personas,amigo1)) && (persona2 = buscar(personas,amigo2)))
{
if(persona1->clase == persona2->clase)
else
}
else
}
}
destruir_personas(&personas);
for(num_personas = 0 ; num_personas < DIM / 2 ; num_personas++)
destruir_clase(&(clases[num_personas]));
}
int main(int argc, char *argv[])
{
//problema_interactivo();
problema_aleatorio();
return 0;
}