Foro de elhacker.net

Hola que tal a todos!!
llevo horas quemandome la cabeza y aun no encuetro una solucion optima para este problema, podras ayudarme? te lo agradeceria mucho.

este es el problema:
Amigos Interactivos

      Límite de memoria   128MB
                Límite de tiempo (caso)   1s   
                Límite de tiempo (total)   60s
Existe una serie de personas definidas en un espacio, dichas personas tienen la capacidad nata de comuncarse entre ellas y formar relaciones sociales, sin embargo hay relaciones muy especiales que dicen llamarce amistad, dichos individuos son conciderados amigos si realizan algun tipo de saludo especial. Una empresa de analisis de comportamiento humano te ha pedido que les ayudes a saber si un individuo A es amigo de un individuo B., un dato curioso es que si existen tres invidividuos A, C, B pertenecientes al espacio, y A es amigo de C y C amigo de B, se genera un lazo mistico mediante el cual A y B son amigos, aunque pudieren no conocerse.

Problema

Dada una descripcion de los sucesos que existen durante la estancia de N individuos en un espacio definido, responder secuencialmente a las preguntas fornuladas, de manera tal que se sepa si en algun momento un indiviuo es amigo del otro.

Entrada

Un unico numero N indicando la cantidad de Individuos

Un numero M indicando la cantidad de preguntas o sucesos que acontecen

Las siguientes M lineas contendran una letra 'P' seguida de dos enteros A y B de tal modo que se debera saber si A es amigo de B en base a los saludos que hallan sido registrados hasta el momento, en caso contrario, una letra 'S' seguida de dos numero A y B indicando que el individuo Ase ha saludado con el individuo B

Ejemplo:
Entrada   Salida
5 8  
 S 1 2  
 S 2 3  
 P 2 4  
 S 4 5  
 P 5 3  
 S 5 1  
 P 2 4  
 P 5 3
Salida

Un numero en una linea por cada pregunta dada en la entrada con un 1 si es que son amigos y un cero en caso contrario

Ejemplo:
Entrada   Salida
0  
 0  
 1  
 1
Límites

0< N < 100,000

0<M < 100,000

por el momento lo que llevo pensado es lo siguiente:
crear un array del tamaño de los amigos donde ese array almacenara vectores.
ahora como en el ejemplo meten un saludo de las personas 1 y 2.
en el vector de la persona 1 meto el 2
en el vector de la persona 2 meto el 1
con esto se que ambos se conocen.
ahora meten un salud de las personas 2 y 3.
hago lo mismo que arriba pero si nos damos cuenta tambien deben conocerse 1 y 3 asi que debo hacer algo mas.
aqui segun yo lo complicado:
          hago un for que recorra los amigos amigos de "a" donde a cada amigo de "a"
          le agrego un amigo de "a" que no tenga (por el lazo misterioso que mencionan        en el el problema)
por ejemplo:
en este caso el amigo a es 2 que tiene de amigos 1 y 3.
recorro el 2 llego al 1 y checo es amigo de 3 ? no, entonces añadelo
ahora llego al tres y checo es amigo de 1 ? no, entonces añadelo
bueno eso es todo lo que llevo ahora el codigo, que aun no acabo mi idea por lo que les mencione arriba:

#include<bits/stdc++.h>
using namespace std;
typedef struct arrays{
    vector<int>amigos;
}persona;
int main(){    
    bool encontrado;
    char opcion;
    int individuos, preguntas, a, b;
    int i, j, k, l;
    cin>>individuos>>preguntas;
    persona ar[individuos + 1];
    for(i = 0; i < preguntas; i++){
        cin>>opcion>>a>>b;
        if(opcion == 'S'){
            ar[a].amigos.push_back(b);
            ar[b].amigos.push_back(a);
            for(j = 1; j < ar[a].amigos.size(); j++)                
                for(k = j + 1; k < ar[a].amigos.size() + 1; k++)
                    for(l = 0; l < ar[j].amigos.size(); l++)
 
 
        }
        else{
 
        }
    }
    return 0;
}
 

si se les ocurre una idea mejor a la mia por favor!! avisenme!!!

a.k.a Facebook
 :silbar: :silbar:


A lo qu yo entendi esto no es asi, a no ser que este mal redactado o mal traducido. Ya que con solo unir un conjunto de elementos con otros tendrias que agregar todos y cada uno de los elementos a todos los elementos del otro conjunto y viceversa.

Lo que entiendo es que una vez que los vas dando de alta y te pregunten por A o B tu  veas si en ese momento se cumple esa relacion "magica" de amistad.

Pero en cualquiera de los casos, Ya sea de la forma en la que tu lo piensas o yo lo estoy pensando. En Ambos se resuelve con un GRAFO.

En tu caso solo es necesario saber si existe una ruta del nodo A al nodo B

y en mi caso si existe y si su profundidad es de al menos 2

Dado que te imponen tiempos y limite de memoria el problema se trata de complejidad de algoritmo...

Se puede resolver usando un Grafo. Se llena un grafo con los saludos y cuando pregunten por X relacion hay que buscar en el grafo si existe un camino del individuo A a B y si es asi evaluar la ruta mas corta si el numero de saltos o nodos entre A y B es menor o igual a 2.

Si esto es asi entonces A y B son amigos.

Tienes que usar el algoritmo de disjktra.

Saludos

---

Edito acabo de realizar el programa usando una simplicacion de grafos y búsqueda pero tengo una duda.

Es la  salida de tu primer ejemplo?

Ya que no veo como puede estar conectado 2 con 4 o el ultimo caso 5 con 3 (usando solo un conocido en comun)

por cierto el principal problema es la busqueda de la relacion entre los individuos (nodos)
 ya que si el peor de los casos tiene 100,000 entradas ai lo buscas iterarivamente 100000 veces vas a tardar mas de 1 segundo por caso.

Mi recomendacion seria combinar alguna otra forma de busqueda mas rapida por ejemplo arboles binarios.

En lo que llegue a mi trabajo pego el codigo.

Saludos

---

Edito nuevamente (Estos ejercicios me gustan mucho)

Recomiendo generar una entrada que realmente estrese el procesador

Hice este codigo que genera el maximo de 100,000 inputs al azar

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
 
#define MAX 100000
 
int main()	{
	register int i = 0;
	srand(time(NULL));
	printf("%i %i\n",MAX,MAX);
	while(i < MAX)	{
		printf("%c ",(rand()%2) ? 'P':'S');
		printf("%i %i\n",1+ rand()%MAX,1+ rand()%MAX);
		i++;
	}
}

Y con ese entrada, mi codigo encuentra todas las posibilidades en 1.08 segundos.

La solución que use como les comente es un arbol y búsqueda binaria entre nodos individuales.


No pongo el código del programa por si hay algún otro interesado no afectar su programación.

Saludos!

muchísimas gracias alberto por responder!!
explicare la salida:
lo primero ya lo dije la relación de 1, 2 y 3.
preguntan 2 conoce a 4 ? no, porque ni siquiera se ha mencionado a 4.
luego preguntan por 5 y 3 como 5 solo es amigo de 4 no hay ninguna relacion asi que no son amigos.
ahora se saludan 4 y 5 esto es como el primer caso donde se saludan 1 y 2.
por ultimo se saludan 5 y 1, aqui la magia, todos los amigos de 1 serán amigos de 5, y como vimos 4 es amigo de 5, asi que todos los amigos de 5 seran amigos de 4, entonces por eso queda la salida queda asi:

0
0
1
1

y si nos damos cuenta al final todos se conocen  :o
mira este el link del problema es un juez en linea https://omegaup.com/arena/problem/am#problems

también gracias por el código lo usare una vez que acabe mi programa.
si alguien puede resolverlo por favor comparta su respuesta, yo si lo acabo lo compartiré.
un saludo!!.

---

oye y respecto a la implementacion:
¿se puede usar un arbol binario de prioridades?
(priority binary tree)

Pues a mi me parece algo incorrecta la forma de interpretar la lectura ya que ahi hablan de solo u  amigo en comun.

Y la implementacion esta hablando del amigo del amigo del amigo.

EN FIN...

La implementacion podria ser cualquier arbol binario para optimizar las busquedas aunque el hecho de tener un arbol por individuo usa mucha memoria.

En minuto mas pongo mi implementacion ( La cual solo aborda el primer ejemplo que yo dije donde solo valido a los amigos del primer amigo)

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<stdbool.h>
 
#define MAXLINE 40
 
struct nodo_arbol	{
	struct nodo_arbol *padre,*derecho,*izquierdo;
	int valor;
};
 
struct nodo	{
	int id;
	int *relations;
	int total;
	struct nodo_arbol *arbol;
};
 
struct nodo **todos = NULL;	//Futuro arreglo de todos los nodos existente
 
void add_relation(int A,int B);
bool existe_salto(int A,int B);
 
struct nodo_arbol *crear_nodo_arbol(struct nodo_arbol *padre,int valor);
struct nodo_arbol *buscar_nodo_arbol(struct nodo_arbol *arbol,int valorAbuscar);
struct nodo_arbol *agregar_valor_arbol(struct nodo_arbol *arbol,int valor);
 
 
int main()	{
	FILE *in = NULL;
	char *line = NULL;
	char *delim = " \n";
	char *token;
	char caso;
	int N,M,i,A,B;
	in = fopen("amistad.in","r");
	line = calloc(MAXLINE,1);
	fgets(line,MAXLINE,in);
	token = strtok(line,delim);
	N = strtol(token,NULL,10);
	todos = calloc(sizeof(struct nodo*),N);		//Reservamos espacio para al menos N apuntadores a los nodos	
	token = strtok(NULL,delim);
	M = strtol(token,NULL,10);
	i = 0;
	while(i < M)	{
		memset(line,0,MAXLINE);
		fgets(line,MAXLINE,in);
		token = strtok(line,delim);
		caso = token[0];
		token = strtok(NULL,delim);
		A = strtol(token,NULL,10);
		A--;
		token = strtok(NULL,delim);
		B = strtol(token,NULL,10);
		B--;
		switch(caso){
			case 'P':
				//printf("P %i %i\n",A+1,B+1);
				if(todos[A] && todos[B])	{	// Ambos nodos son Validos, entonces hay que buscar si existe al menos un camino de a A a B
					if(existe_salto(A,B))	{
						printf("1\n");
					}
					else	{
						printf("0\n");
					}
				}
				else	{	// Uno de los nodos es NULL entonces no existe camino de A a B
					//printf("Un nodo es invalido\n");
					printf("0\n");
				}
			break;
			case 'S':
				//printf("S %i %i\n",A+1,B+1);
				add_relation(A,B);
			break;
		}
		i++;
	}
	fclose(in);
	return 0;
}
 
void add_relation(int A,int B)	{
	if(todos[A] != NULL)	{
		//Nodo ya inicializado;
		todos[A]->relations = realloc(todos[A]->relations,sizeof(int)*(todos[A]->total+1));
		todos[A]->relations[todos[A]->total] = B;
		todos[A]->arbol = agregar_valor_arbol(todos[A]->arbol,B);
		todos[A]->total++;	//incrementamos el numero total de relaciones que tiene este nodo
	}
	else	{
		//Nodo no inicializado
		todos[A] = calloc(sizeof(struct nodo),1);
		todos[A]->id  = A; //Esto es mera formalidad, ya que actualmente el indice del arreglo ya es el mismo "id"
		todos[A]->relations = realloc(todos[A]->relations,sizeof(int)*(todos[A]->total+1));
		todos[A]->relations[todos[A]->total] = B;
		todos[A]->arbol = agregar_valor_arbol(todos[A]->arbol,B);
		todos[A]->total++;	//incrementamos el numero total de relaciones que tiene este nodo
	}
	if(todos[B] != NULL)	{
		//Nodo ya inicializado;
		todos[B]->relations = realloc(todos[B]->relations,sizeof(int)*(todos[B]->total+1));
		todos[B]->relations[todos[B]->total] = A;
		todos[B]->arbol = agregar_valor_arbol(todos[B]->arbol,A);
		todos[B]->total++;	//incrementamos el numero total de relaciones que tiene este nodo
	}
	else	{
		//Nodo no inicializado
		todos[B] = calloc(sizeof(struct nodo),1);
		todos[B]->id  = B; //Esto es mera formalidad, ya que actualmente el indice del arreglo ya es el mismo "id"
		todos[B]->relations = realloc(todos[B]->relations,sizeof(int)*(todos[B]->total+1));
		todos[B]->relations[todos[B]->total] = A;
		todos[B]->arbol = agregar_valor_arbol(todos[B]->arbol,A);
		todos[B]->total++;	//incrementamos el numero total de relaciones que tiene este nodo
 
	}		
}
 
bool existe_salto(int A,int B)	{
	bool r = false;
	struct nodo *nodo_a = NULL,*nodo_b =NULL,*inicio =NULL,*pivote = NULL;
	struct nodo_arbol *busqueda = NULL;
	register int i,j,buscar;
	nodo_a = todos[A];
	nodo_b = todos[B];
	if(nodo_a->total < nodo_b->total)	{
		//printf("Menor A %i\n",A+1);
		inicio = nodo_a;
		buscar = B;
	}
	else	{
		//printf("Menor B %i\n",B+1);
		inicio = nodo_b;
		buscar = A;
	}
	i = 0;
	//printf("Nodos: "); 
	while(i < inicio->total && !r)	{
		//printf("%i\t ",inicio->relations[i]+1);
		busqueda = buscar_nodo_arbol(inicio->arbol,buscar);
		if(busqueda)	{
			r = true;
		}
		i++;
	}
	//printf("\n");
	if(!r)	{
		i = 0;
		while(i < inicio->total && !r)	{
			pivote = todos[inicio->relations[i]];
			j = 0;
			//printf("Nodos de %i:  ",inicio->relations[i]+1); 
			while(j < pivote->total && !r)	{
				busqueda = buscar_nodo_arbol(pivote->arbol,buscar);
				//printf("%i\t ",pivote->relations[j]+1);
				if(busqueda)	{
					r = true;
				}
				j++;
			}		
			//printf("\n");
			i++;
		}		
	}	
	return r;
}
 
 
struct nodo_arbol *crear_nodo_arbol(struct nodo_arbol *padre,int valor)	{
	struct nodo_arbol *n = calloc(sizeof(struct nodo_arbol),1);
	if(n == NULL)	{
		printf("Error de Memoria\n");
		exit(0);
	}
	n->padre = padre;
	n->valor = valor;
	return n;
}
 
struct nodo_arbol *agregar_valor_arbol(struct nodo_arbol *arbol,int valor)	{
	struct nodo_arbol *temp,*pivote;
	int derecho = 0;
	if(arbol)	{
		temp =arbol;
		while(temp != NULL)	{
			pivote = temp;
			if(valor > temp->valor)	{
				temp = temp->derecho;
				derecho = 1;
			}
			else	{
				temp = temp->izquierdo;
				derecho = 0;
			}
		}
		temp = crear_nodo_arbol(pivote,valor);
		if(derecho)	{
			pivote->derecho = temp;
		}
		else	{
			pivote->izquierdo = temp;
		}
		return arbol;
	}
	else	{
		temp = crear_nodo_arbol(NULL,valor);
		return temp;
	}
}
 
struct nodo_arbol *buscar_nodo_arbol(struct nodo_arbol *arbol,int valorAbuscar)	{
	struct nodo_arbol *temp = NULL,*pivote = NULL;
	int entrar = 1;
	temp =arbol;
	while(entrar == 1  && temp != NULL)	{
		pivote = temp;
		if(valorAbuscar == temp->valor){
			entrar = 0;
		}
		else	{
			if(valorAbuscar > temp->valor)	{
				temp = temp->derecho;
			}
			else	{
				temp = temp->izquierdo;
			}
		}
	}
	return temp;
}

Solo habria que extenderla para que revise todos los nodos.

Saludoa

El titulo debe ser Descriptivo, te explico



Describe tanto el tema como


Es decir, no lo describe...

Titulos sugeridos:



Saludos

Alberto muchas gracias por compartir tu respuesta y por la propuesta.
Mira la verdad no entiendo mucho el tema de los arboles binarios, solo he creado uno (hace 1 semama aprox.)y pues conozco muy pocas cosas, ademas de que usas cosas nuevas para mi como calloc, strtok , strtol, etc..
Pero me esforzare mucho en tratar de entenderlo.
En cuanto a mi, les comparto mi respuesta ya la envie a la pagina y me da estos resultados:
Status: Tiempo Limite Excedido.
Porcentaje: 90%.
Memoria: 48.98 MB.
Tiempo: >2.78 s.
Como ven es buena respuesta pues me da el 90%.
Y ahora explicare que fue lo que hice:
Después de buscar en internet me encontré con el set que es un contenedor asociativo que tiene la característica de no guardar valores repetidos y los guarda en orden.
entonces aqui reemplazaba los vectores por los sets.
ahora, lo mas complicado es donde se saludan lo explique anteriormente, ahora lo hare mejor:
se saluda 1 y 2.
en el set de 1 pongo el 2.
en el set de 2 pongo el 1.
ahora recorro el set de 1 y a los amigos de 1 les agregare los amigos de 1, lo mismo hago con el 2, pero como ambos sets tienen un solo elemento que son 1 y 2 respectivamente no pasa nada.
se saluda 2 y 3.
en el set de 2 pongo el 3.
en el set de 3 pongo el 2.
ahora recorro el set de 2 y a sus amigos les añado los amigos de 2.
lo mismo hago con el 3.
entonces hasta ahora los sets quedan asi:
persona:                 conocidos:
   1                              2,3
   2                              1,3
   3                              1,2
preguntan 2 conoce a 4 ?
checo, si cualquier set esta vacio (A o B)entonces quiere decir que no, pues no a saludado a nadie, sino recorro el set de la persona A y busco si esta la persona B.
en este caso es NO.
se saluda 4 y 5.
en el set de 4 pongo el 5.
en el set de 5 pongo el 4.
ahora recorro el set de 4 y a los amigos de 4 les agregare los amigos de 4, lo mismo hago con el 5, pero como ambos sets tienen un solo elemento que son 4 y 5 respectivamente no pasa nada.
entonces hasta ahora los sets quedan asi:
persona:                 conocidos:
   1                              2,3
   2                              1,3
   3                              1,2
   4                              5
   5                              4  
ahora preguntan 5 conoce a 3?
checo, si cualquier set esta vacio (A o B) entonces quiere decir que no, pues no a saludado a nadie, sino recorro el set de la persona A y busco si esta la persona B.
en este caso es NO.
Por ultimo se saluda 5 con 1.
en el set de 5 pongo el 1.
en el set de 1 pongo el 5.
ahora recorro el set de 5 y a todos sus amigos les añado los amigos que no tengan de 5, lo mismo hago con el 1 y si nos damos cuenta ya todos son amigos, por ende las siguientes preguntas son SI.
Aqui les dejo el codigo:

#include<bits/stdc++.h>
using namespace std;
                            /*DECLARO TODO LO QUE USARE DE SET Y EL VECTOR QUE GUARDARA LAS RESPUESTAS*/
typedef struct arrays{
    set<int>amigos;
}ar;
     set<int>::iterator j;
     set<int>::iterator k;
     vector<string>respuestas;
 
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    bool encontrado;
    char opcion;
    int personas, comandos, a, b;
    int i, l, z;
    cin>>personas>>comandos;
 
    ar persona[personas + 1]; /*CREAMOS UN ARRAY DE SETS DE TAMAÑO PERSONAS*/
 
    for(i = 0; i < comandos; i++){
        cin>>opcion>>a>>b;
        if(opcion == 'S'){
            persona[a].amigos.insert(b);
            persona[b].amigos.insert(a);
            for(j = persona[a].amigos.begin(); j != persona[a].amigos.end(); j++){ /* PERSONA A*/
                for(k = persona[a].amigos.begin(); k != persona[a].amigos.end(); k++){
                    persona[*j].amigos.insert(*k);
                }
            }
            for(j = persona[b].amigos.begin(); j != persona[b].amigos.end(); j++){ /*PERSONA B*/
                for(k = persona[b].amigos.begin(); k != persona[b].amigos.end(); k++){
                    persona[*j].amigos.insert(*k);
                }
            }
        }
        else{
            if(persona[a].amigos.empty() || persona[b].amigos.empty())
                respuestas.push_back("0\n");
            else{
                encontrado = false;
                for(j = persona[a].amigos.begin(); j != persona[a].amigos.end(); j++){/*BUSCAMOS SI EN LOS AMIGOS DE A ESTA B*/
                    if(*j == b){
                        encontrado = true;
                        break;
                    }
                }
                if(encontrado)
                    respuestas.push_back("1\n");
                else
                    respuestas.push_back("0\n");
            }
        }
    }
    for(i = 0; i < respuestas.size(); i++)
        cout<<respuestas[i];
    return 0;
}

Creo que si optimizamos la búsqueda de la persona B en A y al agregar amigos podría dar el 100%
Encontre en internet algo llamado set_union y merge para eso de añadir los amigos pero eso de buscar los amigos pensaba en una búsqueda binario aunque según yo que no es posible.

Hola.


Los arboles binarios por su diseño implementan una busqueda binaria


Si lo quieres manejar manualmente en un array tendrias que ordenarlos para posteriormente hacer una búsqueda binaria.

Calcule la memoria que usaria mi codigo y seria cerca de 2 MB en el peor de los casos (100000) inputs.

hay veces que me complico programando en C ya que me gusta saber que hace exactamente el codigo. Lo que tu haces con un simple cin>>  yo lo hago como con 10 lineas de codigo y au que son muchas lineas siento que se ejecuta igual de rapido que un cin o incluso mas rapido aun...

Busca como implementar una busqueda binaria y el algoritmo de disjktra es lo mas rapido que vas a encontrar y terminarias usando menos memoria.

Voy a adaptar mi codigo a C++ para que veas como funciona.

Mientras te dejo unos videos que hice de arboles binarios

BBsgYwXGdI8

hlWvK1EU-oA

Saludos

Alberto un pregunta en cuanto a tu video, como te comente ya habia hecho un arbol binario, pero yo en la estructura del nodo solo habia utilizado el dato y los dos punteros izquierdo y derecho, mi pregunta es ¿Para que sirve el nodo padre?
Bueno y otra duda, en tu arbol binario del problema quien es la raiz o como funciona eso de ir añadiendo nodos (disculpa mi ignorancia)?
Mira este es mi codigo:

#include <bits/stdc++.h>
using namespace std;
 
struct nodoArbol {
 struct nodoArbol *ptrIzq;
 int dato;
 struct nodoArbol *prtDer;
};
 
typedef struct nodoArbol NodoArbol;
typedef NodoArbol *ptrNodoArbol;
 
void insertaNodo( ptrNodoArbol *ptrArbol, int valor ){
 
    if (*ptrArbol == NULL) { /*ARBOL VACIO*/
        *ptrArbol = (NodoArbol*)malloc(sizeof(NodoArbol));
        (*ptrArbol)->dato = valor;
        (*ptrArbol)->ptrIzq = NULL;
        (*ptrArbol)->prtDer = NULL;
    }
 
    else {
        /* el dato a insertar es menor que el dato en el nodo actual */
        if (valor < (*ptrArbol)->dato) {
            insertaNodo(&((*ptrArbol)->ptrIzq), valor);
        }
        else if (valor > (*ptrArbol)->dato) {
            insertaNodo(&((*ptrArbol)->prtDer), valor);
        }
    }
}
 
void inOrden(ptrNodoArbol ptrArbol){
    if (ptrArbol != NULL) {
        inOrden(ptrArbol->ptrIzq);
        cout<<ptrArbol -> dato<<" ";
        inOrden(ptrArbol->prtDer);
    }
}
 
void preOrden(ptrNodoArbol ptrArbol){
    if (ptrArbol != NULL){
        cout<<ptrArbol -> dato<<" ";
        preOrden(ptrArbol->ptrIzq);
        preOrden(ptrArbol->prtDer);
    }
}
 
void postOrden(ptrNodoArbol ptrArbol) {
    if (ptrArbol != NULL){
        postOrden(ptrArbol->ptrIzq);
        postOrden(ptrArbol->prtDer);
        cout<<ptrArbol -> dato<<" ";
    }
}
 
int main(){
 
    ptrNodoArbol ptrRaiz = NULL;
    int limite,elemento;
    cout<<"INTRODUCE CUANTOS ELEMENTOS TENDRA EL ARBOL: ";
    cin>>limite;
 
    for (int i = 1; i <= limite; i++) {
        cout<<"INGRESE ELEMENTO: ";
        cin>>elemento;
        insertaNodo(&ptrRaiz, elemento);
    }
 
    cout<<"\nEL RECORRIDO EN PREORDEN ES:\n";
    preOrden(ptrRaiz);
 
    cout<<"\nEL RECORRIDO EN INORDEN ES:\n";
    inOrden(ptrRaiz);
 
    cout<<"\nEL RECORRIDO EN POSTORDEN ES:\n";
    postOrden(ptrRaiz);
 
    return 0;
}

Gracias por tu ayuda.

La raiz es el primer nodo que se inserta..

Su padre es null.

Tus funciones de inOrden o preorden son recursivas y no necesitan saber quien es el padre, aun asi gastan mas memoria. En funciones iterativas es mecesario saber quien es el podre y gastan menos memoria.

En ocasiones es necesario separar subarboles o eliminar arboles completos, y tambien facilita mucho tener una referencia al padre.

Basicamente es una facilidad tener esa referencia en fumciones iterarivas.

Como reto deberias de hacer tu funcion inOrden y preOrden de forma iterativa, Esto es sin llamar a las funciones dichas desde si mismas.

Saludos!

Interesante ejercicio.

Se trata de crear particiones sobre el conjunto de personas (tenemos una relación de equivalencia en un conjunto->la equivalencia crea una partición del conjunto (un conjunto de subconjuntos disjuntos)).

Se me ocurre que se puede tener un vector (mejor árbol, que así no hay que estar desplazando valores para mantener el orden después de una inserción) con pares del tipo numero_persona-clase. Así la cuestión de decidir si dos personas son amigos se reduce a realizar la búsqueda de las dos personas y ver si pertenecen a la misma clase, y la inserción se podría hacer en un vector (sabemos que el máximo numero de parejas es 100.000 / 2) en el que cada componente sea un vector de punteros a los nodos del árbol que formen parte de la misma clase. Así, a través de los punteros de la tabla, si hubiese que fusionar dos clases sería muy fácil corregir directamente en cada nodo del árbol la clase a la que pertenece el par persona-clase. La tabla mantiene una lista de todas las personas relacionadas entre sí y soluciona el problema de buscar en el árbol todas las personas que pertenecen a la misma clase.

A ver que sale de esta idea.

¡Saludos!


Con el planteamiento anterior, cambiando la idea de un vector de vectores por la de un vector de árboles, en mi ordenador, el tiempo de ejecución en el caso de la entrada de mayor dimensión se pasa del segundo por poco. Entre 1'2 y 1'3 segundos.

Alberto, te mando el código por MP, como los planteamientos son distintos me gustaría ver tu código.

¡Saludos!

 ;-) ;-)  ;-)

Excelente aproximacion. Aun no veo tu codigo pero.... la idea es genial y de hecho es mas rápido que un Grafo con Disjktra...

Fucionar arboles seria mas rapido y las consultas prácticamente ya están hechas al tener un valor que nos indiqué a que conjunto o "arbol" pertenece un nodo facilmente se puede saber si existe ese lazo o no.

En lo que llegue al trabajo te pado mi codigo.

Saludos

Bueno... hoy estoy muy tonto. Pensaba que en los códigos anteriores discutíais sobre opciones para resolver el problema. Veo que ya hay alguna solución, así que dejo la mía también. main está al final y justo antes están las funciones problema_interactivo y problema_aleatorio. La primera solicita los datos desde el teclado, la segunda genera 100.000 casos aleatorios y los procesa.

#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);
	free(*personas);
 
	*personas = NULL;
}
 
void destruir_clase(NodoArbolPersona **amigos)
{
	if(!(*amigos))
		return;
 
	destruir_personas(&((*amigos)->menores));
	destruir_personas(&((*amigos)->mayores));
 
	free(*amigos);
 
	*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);
	scanf("%d", &num_casos);
	while(getchar() != '\n');
 
	while(num_casos--)
	{
		scanf("%c%d%d", &operador, &amigo1, &amigo2);
		while(getchar() != '\n');
 
		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)
						printf("1\n");
					else
						printf("0\n");
				}
				else
					printf("0\n");
		}
	}
 
	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];
 
	srand(time(NULL));
 
	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)
						printf("1\n");
					else
						printf("0\n");
				}
				else
					printf("0\n");
		}
	}
 
	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;
}
 

Hola!

Dejo aqui mis 2 implementaciones

La primera con Un Grafo y Disjktra simplificado

Y la segunda como lo sugirio do-while con un arbol y una referencia a que arbol/clase/conjunto pertenece cada nodo (Esta última es la mas rapida)

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<stdbool.h>
#include<time.h>
 
 
#define MAXLINE 40
 
struct nodo_arbol	{
	struct nodo_arbol *padre,*derecho,*izquierdo;	// 12 u 24 bytes
	int valor;										// 4 bytes
};									//Total				16 u 28 bytes por Nodo
									//peor Caso 28 bytes * 100,000 nodos = ~2.8 MB
 
struct nodo	{
	int id;						//4 bytes
	int *relations;				//4 ú 8 bytes
	int total;					//4 bytes
	struct nodo_arbol *arbol;	//4 ú 8 bytes
	int offset;
	int visitado;
};					//Total			16 u 24 bytes por Nodo
					///peor Caso 24 bytes * 100,000 nodos = ~2.40 MB
 
struct nodo **todos = NULL;	//Futuro arreglo de todos los nodos existente
							//4 y 8 bytes
							//Peor caso 8 bytes * 100,000   = ~800 KB	
 
void add_relation(int A,int B);
bool existe_salto(int A,int B);
 
struct nodo_arbol *crear_nodo_arbol(struct nodo_arbol *padre,int valor);
struct nodo_arbol *buscar_nodo_arbol(struct nodo_arbol *arbol,int valorAbuscar);
struct nodo_arbol *agregar_valor_arbol(struct nodo_arbol *arbol,int valor);
 
 
int main()	{
	FILE *in = NULL;
	char *line = NULL;
	char *delim = " \n";
	char *token;
	char caso;
	int N,M,i,A,B;
	in = fopen("amistad.in","r");	//Archivo ¬¬
	srand(time(NULL));	// Para los nodos visitados...
	line = calloc(MAXLINE,1);
	//Leemos la primera linea
	fgets(line,MAXLINE,in);
	token = strtok(line,delim);
	N = strtol(token,NULL,10);
	todos = calloc(sizeof(struct nodo*),N);		//Reservamos espacio para al menos N apuntadores a los nodos	
	token = strtok(NULL,delim);
	M = strtol(token,NULL,10);
	//Leemos las siguientes M lineas y evaluamos
	i = 0;
	while(i < M)	{
		memset(line,0,MAXLINE);
		//Leemos la M,esima linea
		fgets(line,MAXLINE,in);
		token = strtok(line,delim);
		caso = token[0];
		token = strtok(NULL,delim);
		A = strtol(token,NULL,10);
		A--;
		token = strtok(NULL,delim);
		B = strtol(token,NULL,10);
		B--;
		//Evaluamos
		switch(caso){
			case 'P':
				//printf("P %i %i\n",A+1,B+1);
				if(todos[A] && todos[B])	{	// Ambos nodos son Validos, entonces hay que buscar si existe al menos un camino de a A a B
					if(existe_salto(A,B))	{
						printf("1\n");
					}
					else	{
						printf("0\n");
					}
				}
				else	{	// Uno de los nodos es NULL entonces no existe camino de A a B
					//printf("Un nodo es invalido\n");
					printf("0\n");
				}
			break;
			case 'S':
				//printf("S %i %i\n",A+1,B+1);
				add_relation(A,B);
			break;
		}
		i++;
	}
	fclose(in);
	return 0;
}
 
void add_relation(int A,int B)	{
	if(todos[A] != NULL)	{
		//Nodo ya inicializado;
		todos[A]->relations = realloc(todos[A]->relations,sizeof(int)*(todos[A]->total+1));
		todos[A]->relations[todos[A]->total] = B;
		todos[A]->arbol = agregar_valor_arbol(todos[A]->arbol,B);
		todos[A]->total++;	//incrementamos el numero total de relaciones que tiene este nodo
	}
	else	{
		//Nodo no inicializado
		todos[A] = calloc(sizeof(struct nodo),1);
		todos[A]->id  = A; //Esto es mera formalidad, ya que actualmente el indice del arreglo ya es el mismo "id"
		todos[A]->relations = realloc(todos[A]->relations,sizeof(int)*(todos[A]->total+1));
		todos[A]->relations[todos[A]->total] = B;
		todos[A]->arbol = agregar_valor_arbol(todos[A]->arbol,B);
		todos[A]->total++;	//incrementamos el numero total de relaciones que tiene este nodo
		todos[A]->visitado = 0;
		todos[A]->offset = 0;
	}
	if(todos[B] != NULL)	{
		//Nodo ya inicializado;
		todos[B]->relations = realloc(todos[B]->relations,sizeof(int)*(todos[B]->total+1));
		todos[B]->relations[todos[B]->total] = A;
		todos[B]->arbol = agregar_valor_arbol(todos[B]->arbol,A);
		todos[B]->total++;	//incrementamos el numero total de relaciones que tiene este nodo
 
	}
	else	{
		//Nodo no inicializado
		todos[B] = calloc(sizeof(struct nodo),1);
		todos[B]->id  = B; //Esto es mera formalidad, ya que actualmente el indice del arreglo ya es el mismo "id"
		todos[B]->relations = realloc(todos[B]->relations,sizeof(int)*(todos[B]->total+1));
		todos[B]->relations[todos[B]->total] = A;
		todos[B]->arbol = agregar_valor_arbol(todos[B]->arbol,A);
		todos[B]->total++;	//incrementamos el numero total de relaciones que tiene este nodo
		todos[B]->visitado = 0;
		todos[B]->offset = 0;
	}		
}
 
//A.k.a diskjtra simplificado a aristas de valor 1 y solo valida que exista la union
bool existe_salto(int A,int B)	{
	bool r = false,outs = false;
	struct nodo *nodo_a = NULL,*nodo_b =NULL,*inicio =NULL,*pivote = NULL;
	struct nodo_arbol *busqueda = NULL;
	struct nodo **pendientes = NULL;
	register int i,j,buscar,total = 0;
	int visitado;
	visitado = rand();
	nodo_a = todos[A];
	nodo_b = todos[B];
	if(nodo_a->total < nodo_b->total)	{
		inicio = nodo_a;
		buscar = B;
		//printf("Menor A %i\n",inicio->id+1);
	}
	else	{
		inicio = nodo_b;
		buscar = A;
		//printf("Menor B %i\n",inicio->id+1);
	}
	//printf("Nodos: "); 
	i = 0;
	pendientes = realloc(pendientes,sizeof(struct nodo*)*(total+1));
	pendientes[total] = inicio;
	total++;
	while(!r && i < total)	{
		pivote = pendientes[i];
		pivote->visitado = visitado;
		//printf("Visitando %i\n",pivote->id+1);
		busqueda = buscar_nodo_arbol(pivote->arbol,buscar);
		if(!busqueda)	{
			//printf("El nodo %i no tiene el nodo buscado %i\n",pivote->id+1,buscar+1);
			j = 0;
			while(j < pivote->total )	{
				if(todos[pivote->relations[j]]->visitado != visitado)	{
					//printf("Anexando el nodo %i para su posterior visita\n",todos[pivote->relations[j]]->id+1);
					pendientes = realloc(pendientes,sizeof(struct nodo*)*(total+1));
					pendientes[total] = todos[pivote->relations[j]];
					total++;
				}
				j++;
			}
		}
		else	{
			//printf("El nodo %i SI tiene el nodo buscado %i\n",pivote->id+1,buscar+1);
			r = true;
		}
		i++;
	}
	free(pendientes);
	return r;
}
 
//Funciones de Arbol (Solo como almacenamiento y busqueda rapida)
 
struct nodo_arbol *crear_nodo_arbol(struct nodo_arbol *padre,int valor)	{
	struct nodo_arbol *n = calloc(sizeof(struct nodo_arbol),1);
	if(n == NULL)	{
		printf("Error de Memoria\n");
		exit(0);
	}
	n->padre = padre;
	n->valor = valor;
	return n;
}
 
struct nodo_arbol *agregar_valor_arbol(struct nodo_arbol *arbol,int valor)	{
	struct nodo_arbol *temp,*pivote;
	int derecho = 0;
	if(arbol)	{
		temp =arbol;
		while(temp != NULL)	{
			pivote = temp;
			if(valor > temp->valor)	{
				temp = temp->derecho;
				derecho = 1;
			}
			else	{
				temp = temp->izquierdo;
				derecho = 0;
			}
		}
		temp = crear_nodo_arbol(pivote,valor);
		if(derecho)	{
			pivote->derecho = temp;
		}
		else	{
			pivote->izquierdo = temp;
		}
		return arbol;
	}
	else	{
		temp = crear_nodo_arbol(NULL,valor);
		return temp;
	}
}
 
struct nodo_arbol *buscar_nodo_arbol(struct nodo_arbol *arbol,int valorAbuscar)	{
	struct nodo_arbol *temp = NULL,*pivote = NULL;
	int entrar = 1;
	temp =arbol;
	while(entrar == 1  && temp != NULL)	{
		pivote = temp;
		if(valorAbuscar == temp->valor){
			entrar = 0;
		}
		else	{
			if(valorAbuscar > temp->valor)	{
				temp = temp->derecho;
			}
			else	{
				temp = temp->izquierdo;
			}
		}
	}
	return temp;
}

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<stdbool.h>
#include<time.h>
 
#define MAXLINE 40
 
struct nodo_arbol	{
	struct nodo_arbol *padre,*derecho,*izquierdo;
	struct nodo *valor;
};
 
struct arbol	{
	struct nodo_arbol *raiz;
	struct nodo_arbol **nodos;
	int total;
};
 
struct nodo	{
	int id;
	struct arbol *arbol;
};
 
struct nodo **todos = NULL;
 
void add_relation(int A,int B);
bool existe_salto(int A,int B);
struct arbol *funciona_arbol(struct arbol *A,struct arbol *B);
 
struct nodo_arbol *crear_nodo_arbol(struct nodo_arbol *padre,struct nodo *valor);
struct arbol *agregar_valor_arbol(struct arbol *arbol,struct nodo *valor);
 
int main()	{
	FILE *in = NULL;
	char *line = NULL;
	char *delim = " \n";
	char *token;
	char caso;
	int N,M,i,A,B;
	in = fopen("amistad.in","r");	//Archivo ¬¬
	srand(time(NULL));	// Para los nodos visitados...
	line = calloc(MAXLINE,1);
	//Leemos la primera linea
	fgets(line,MAXLINE,in);
	token = strtok(line,delim);
	N = strtol(token,NULL,10);
	todos = calloc(sizeof(struct nodo*),N);		//Reservamos espacio para al menos N apuntadores a los nodos	
	token = strtok(NULL,delim);
	M = strtol(token,NULL,10);
	//Leemos las siguientes M lineas y evaluamos
	i = 0;
	while(i < M)	{
		memset(line,0,MAXLINE);
		//Leemos la M,esima linea
		fgets(line,MAXLINE,in);
		token = strtok(line,delim);
		caso = token[0];
		token = strtok(NULL,delim);
		A = strtol(token,NULL,10);
		A--;
		token = strtok(NULL,delim);
		B = strtol(token,NULL,10);
		B--;
		//Evaluamos
		switch(caso){
			case 'P':
				//printf("P %i %i\n",A+1,B+1);
				if(todos[A] && todos[B])	{	// Ambos nodos son Validos, entonces hay que buscar si existe al menos un camino de a A a B
					if(existe_salto(A,B))	{
						printf("1\n");
					}
					else	{
						printf("0\n");
					}
				}
				else	{	// Uno de los nodos es NULL entonces no existe camino de A a B
					//printf("Un nodo es invalido\n");
					printf("0\n");
				}
			break;
			case 'S':
				//printf("S %i %i\n",A+1,B+1);
				add_relation(A,B);
			break;
		}
		i++;
	}
	fclose(in);
	return 0;
}
 
void add_relation(int A,int B)	{
	struct nodo *nodo_a,*nodo_b;
	if(todos[A] == NULL)	{	// Si no existe A lo inicializamos
		todos[A] = calloc(sizeof(struct nodo),1);
		todos[A]->id  = A;
	}
	if(todos[B] == NULL)	{	// Si no existe B lo inicializamos
		todos[B] = calloc(sizeof(struct nodo),1);
		todos[B]->id  = B;
	}
	nodo_a = todos[A];	
	nodo_b = todos[B];
	if(!nodo_a->arbol && !nodo_b->arbol){	// Si ambos arboles son NULL los inicializamos
		nodo_a->arbol = agregar_valor_arbol(nodo_a->arbol,nodo_a);
		nodo_a->arbol = agregar_valor_arbol(nodo_a->arbol,nodo_b);
	}
	else	{
		if(nodo_a->arbol && !nodo_b->arbol)	{	//Si el arbol de A es valido y el de B no, agregamos B al arbol de A
			nodo_a->arbol =agregar_valor_arbol(nodo_a->arbol,nodo_b);
		}
		else	{
			if(!nodo_a->arbol && nodo_b->arbol){	//Si el arbol de B es valid y el de A no, agregamo A al arbol de B
				nodo_b->arbol =agregar_valor_arbol(nodo_b->arbol,nodo_a);
			}
			else{// En este punto ambos arboles son validos 
				if(nodo_a->arbol != nodo_b->arbol)	{	//Validamos si ambos arboles son distintos
					if(nodo_a->arbol->total < nodo_b->arbol->total)	{	// Evaluamos cual es el arbol con mejor coste de fusion
						nodo_b->arbol = funciona_arbol(nodo_b->arbol,nodo_a->arbol);	//Fucionamos el arbol de A en el arbol de B 
					}
					else	{
						nodo_a->arbol = funciona_arbol(nodo_a->arbol,nodo_b->arbol);	//Fucionamos el arbol de B en el arbol de A
					}
				}
			}
		}
	}
}
 
//Fucinamos el arbol B en el arbol A, y eliminamos B nodo por nodo y finalmente liberamos la estructura Arbol que usamos
struct arbol *funciona_arbol(struct arbol *A,struct arbol *B)	{
	int i = 0;
	while(i<B->total)	{
		B->nodos[i];
		A = agregar_valor_arbol(A,B->nodos[i]->valor);
		free(B->nodos[i]);
		i++;
	}
	free(B);
	return A;
}
 
 
//Evaluar si existe un camino valido de A a B, se reduce a validar si estan en el mismo Arbol o no
bool existe_salto(int A,int B)	{
	struct nodo *nodo_a = NULL,*nodo_b =NULL;
	nodo_a = todos[A];
	nodo_b = todos[B];
	return (nodo_a->arbol == nodo_b->arbol);
}
 
 
//Funcion auxiliar para crear un nodo de arbol
struct nodo_arbol *crear_nodo_arbol(struct nodo_arbol *padre,struct nodo *valor)	{
	struct nodo_arbol *n = calloc(sizeof(struct nodo_arbol),1);
	if(n == NULL)	{
		printf("Error de Memoria\n");
		exit(0);
	}
	n->padre = padre;
	n->valor = valor;
	return n;
}
 
//Agregamos un valor al arbol
struct arbol *agregar_valor_arbol(struct arbol *arbol,struct nodo *valor)	{
	struct nodo_arbol *temp,*pivote;
	int derecho = 0;
	if(arbol)	{
		temp =arbol->raiz;
		while(temp != NULL)	{
			pivote = temp;
			if(valor->id > temp->valor->id)	{
				temp = temp->derecho;
				derecho = 1;
			}
			else	{
				temp = temp->izquierdo;
				derecho = 0;
			}
		}
		temp = crear_nodo_arbol(pivote,valor);
		if(derecho)	{
			pivote->derecho = temp;
		}
		else	{
			pivote->izquierdo = temp;
		}
		valor->arbol = arbol;
		arbol->nodos = realloc(arbol->nodos,sizeof(struct nodo*)*(arbol->total+1));
		arbol->nodos[arbol->total] = temp;
	}
	else	{
		arbol = calloc(sizeof(struct arbol),1);
		arbol->raiz = crear_nodo_arbol(NULL,valor);
		arbol->nodos = realloc(arbol->nodos,sizeof(struct nodo_arbol*)*(arbol->total+1));
		arbol->nodos[arbol->total] = arbol->raiz;
		valor->arbol = arbol;
	}
	arbol->total++;
	return arbol;
}