elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Arreglado, de nuevo, el registro del warzone (wargame) de EHN


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  ¿Mejor algoritmo? Problema con aproximaciones de Grafos
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] 2 Ir Abajo Respuesta Imprimir
Autor Tema: ¿Mejor algoritmo? Problema con aproximaciones de Grafos  (Leído 6,413 veces)
KINGARZA

Desconectado Desconectado

Mensajes: 33

Facebook: Luis Garza


Ver Perfil
¿Mejor algoritmo? Problema con aproximaciones de Grafos
« en: 27 Julio 2016, 09:43 am »

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:
Código
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef struct arrays{
  4.    vector<int>amigos;
  5. }persona;
  6. int main(){    
  7.    bool encontrado;
  8.    char opcion;
  9.    int individuos, preguntas, a, b;
  10.    int i, j, k, l;
  11.    cin>>individuos>>preguntas;
  12.    persona ar[individuos + 1];
  13.    for(i = 0; i < preguntas; i++){
  14.        cin>>opcion>>a>>b;
  15.        if(opcion == 'S'){
  16.            ar[a].amigos.push_back(b);
  17.            ar[b].amigos.push_back(a);
  18.            for(j = 1; j < ar[a].amigos.size(); j++)                
  19.                for(k = j + 1; k < ar[a].amigos.size() + 1; k++)
  20.                    for(l = 0; l < ar[j].amigos.size(); l++)
  21.  
  22.  
  23.        }
  24.        else{
  25.  
  26.        }
  27.    }
  28.    return 0;
  29. }
  30.  
si se les ocurre una idea mejor a la mia por favor!! avisenme!!!


« Última modificación: 28 Julio 2016, 00:36 am por KINGARZA » En línea

AlbertoBSD
Programador y
Moderador Global
***
Desconectado Desconectado

Mensajes: 3.696


🏴 Libertad!!!!!


Ver Perfil WWW
Re: Necesito tu ayuda para resolver un problema en C++
« Respuesta #1 en: 27 Julio 2016, 12:56 pm »

Citar
Una empresa de analisis de comportamiento humano
a.k.a Facebook
 :silbar: :silbar:

Citar
PERO SI NOS DAMOS CUENTA TAMBIEN DEBEN CONOCERSE 1 Y 3 ASI QUE DEBO HACER ALGO MAS.

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.
Citar
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

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

Código
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<time.h>
  4.  
  5. #define MAX 100000
  6.  
  7. int main() {
  8. register int i = 0;
  9. srand(time(NULL));
  10. printf("%i %i\n",MAX,MAX);
  11. while(i < MAX) {
  12. printf("%c ",(rand()%2) ? 'P':'S');
  13. printf("%i %i\n",1+ rand()%MAX,1+ rand()%MAX);
  14. i++;
  15. }
  16. }

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!


« Última modificación: 27 Julio 2016, 17:55 pm por AlbertoBSD » En línea

KINGARZA

Desconectado Desconectado

Mensajes: 33

Facebook: Luis Garza


Ver Perfil
Re: Necesito tu ayuda para resolver un problema en C++
« Respuesta #2 en: 27 Julio 2016, 21:20 pm »

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)

« Última modificación: 27 Julio 2016, 21:30 pm por engel lex » En línea

engel lex
Moderador Global
***
Desconectado Desconectado

Mensajes: 15.514



Ver Perfil
Re: Necesito tu ayuda para resolver un problema en C++
« Respuesta #3 en: 27 Julio 2016, 21:28 pm »

Mod: Lee las reglas del foro y sigue las advertencias!

No escribas en mayúsculas (corregido)
los titulos de los temas deben ser descriptivos!
no hagas doble post!

antes de responder a este tema nuevamente corrige el titulo
En línea

El problema con la sociedad actualmente radica en que todos creen que tienen el derecho de tener una opinión, y que esa opinión sea validada por todos, cuando lo correcto es que todos tengan derecho a una opinión, siempre y cuando esa opinión pueda ser ignorada, cuestionada, e incluso ser sujeta a burla, particularmente cuando no tiene sentido alguno.
AlbertoBSD
Programador y
Moderador Global
***
Desconectado Desconectado

Mensajes: 3.696


🏴 Libertad!!!!!


Ver Perfil WWW
Re: Necesito tu ayuda para resolver un problema en C++
« Respuesta #4 en: 27 Julio 2016, 22:06 pm »

Pues a mi me parece algo incorrecta la forma de interpretar la lectura ya que ahi hablan de solo u  amigo en comun.
Citar
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,

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)

Código
  1. #include<stdio.h>
  2. #include<string.h>
  3. #include<stdlib.h>
  4. #include<stdbool.h>
  5.  
  6. #define MAXLINE 40
  7.  
  8. struct nodo_arbol {
  9. struct nodo_arbol *padre,*derecho,*izquierdo;
  10. int valor;
  11. };
  12.  
  13. struct nodo {
  14. int id;
  15. int *relations;
  16. int total;
  17. struct nodo_arbol *arbol;
  18. };
  19.  
  20. struct nodo **todos = NULL; //Futuro arreglo de todos los nodos existente
  21.  
  22. void add_relation(int A,int B);
  23. bool existe_salto(int A,int B);
  24.  
  25. struct nodo_arbol *crear_nodo_arbol(struct nodo_arbol *padre,int valor);
  26. struct nodo_arbol *buscar_nodo_arbol(struct nodo_arbol *arbol,int valorAbuscar);
  27. struct nodo_arbol *agregar_valor_arbol(struct nodo_arbol *arbol,int valor);
  28.  
  29.  
  30. int main() {
  31. FILE *in = NULL;
  32. char *line = NULL;
  33. char *delim = " \n";
  34. char *token;
  35. char caso;
  36. int N,M,i,A,B;
  37. in = fopen("amistad.in","r");
  38. line = calloc(MAXLINE,1);
  39. fgets(line,MAXLINE,in);
  40. token = strtok(line,delim);
  41. N = strtol(token,NULL,10);
  42. todos = calloc(sizeof(struct nodo*),N); //Reservamos espacio para al menos N apuntadores a los nodos
  43. token = strtok(NULL,delim);
  44. M = strtol(token,NULL,10);
  45. i = 0;
  46. while(i < M) {
  47. memset(line,0,MAXLINE);
  48. fgets(line,MAXLINE,in);
  49. token = strtok(line,delim);
  50. caso = token[0];
  51. token = strtok(NULL,delim);
  52. A = strtol(token,NULL,10);
  53. A--;
  54. token = strtok(NULL,delim);
  55. B = strtol(token,NULL,10);
  56. B--;
  57. switch(caso){
  58. case 'P':
  59. //printf("P %i %i\n",A+1,B+1);
  60. if(todos[A] && todos[B]) { // Ambos nodos son Validos, entonces hay que buscar si existe al menos un camino de a A a B
  61. if(existe_salto(A,B)) {
  62. printf("1\n");
  63. }
  64. else {
  65. printf("0\n");
  66. }
  67. }
  68. else { // Uno de los nodos es NULL entonces no existe camino de A a B
  69. //printf("Un nodo es invalido\n");
  70. printf("0\n");
  71. }
  72. break;
  73. case 'S':
  74. //printf("S %i %i\n",A+1,B+1);
  75. add_relation(A,B);
  76. break;
  77. }
  78. i++;
  79. }
  80. fclose(in);
  81. return 0;
  82. }
  83.  
  84. void add_relation(int A,int B) {
  85. if(todos[A] != NULL) {
  86. //Nodo ya inicializado;
  87. todos[A]->relations = realloc(todos[A]->relations,sizeof(int)*(todos[A]->total+1));
  88. todos[A]->relations[todos[A]->total] = B;
  89. todos[A]->arbol = agregar_valor_arbol(todos[A]->arbol,B);
  90. todos[A]->total++; //incrementamos el numero total de relaciones que tiene este nodo
  91. }
  92. else {
  93. //Nodo no inicializado
  94. todos[A] = calloc(sizeof(struct nodo),1);
  95. todos[A]->id  = A; //Esto es mera formalidad, ya que actualmente el indice del arreglo ya es el mismo "id"
  96. todos[A]->relations = realloc(todos[A]->relations,sizeof(int)*(todos[A]->total+1));
  97. todos[A]->relations[todos[A]->total] = B;
  98. todos[A]->arbol = agregar_valor_arbol(todos[A]->arbol,B);
  99. todos[A]->total++; //incrementamos el numero total de relaciones que tiene este nodo
  100. }
  101. if(todos[B] != NULL) {
  102. //Nodo ya inicializado;
  103. todos[B]->relations = realloc(todos[B]->relations,sizeof(int)*(todos[B]->total+1));
  104. todos[B]->relations[todos[B]->total] = A;
  105. todos[B]->arbol = agregar_valor_arbol(todos[B]->arbol,A);
  106. todos[B]->total++; //incrementamos el numero total de relaciones que tiene este nodo
  107. }
  108. else {
  109. //Nodo no inicializado
  110. todos[B] = calloc(sizeof(struct nodo),1);
  111. todos[B]->id  = B; //Esto es mera formalidad, ya que actualmente el indice del arreglo ya es el mismo "id"
  112. todos[B]->relations = realloc(todos[B]->relations,sizeof(int)*(todos[B]->total+1));
  113. todos[B]->relations[todos[B]->total] = A;
  114. todos[B]->arbol = agregar_valor_arbol(todos[B]->arbol,A);
  115. todos[B]->total++; //incrementamos el numero total de relaciones que tiene este nodo
  116.  
  117. }
  118. }
  119.  
  120. bool existe_salto(int A,int B) {
  121. bool r = false;
  122. struct nodo *nodo_a = NULL,*nodo_b =NULL,*inicio =NULL,*pivote = NULL;
  123. struct nodo_arbol *busqueda = NULL;
  124. register int i,j,buscar;
  125. nodo_a = todos[A];
  126. nodo_b = todos[B];
  127. if(nodo_a->total < nodo_b->total) {
  128. //printf("Menor A %i\n",A+1);
  129. inicio = nodo_a;
  130. buscar = B;
  131. }
  132. else {
  133. //printf("Menor B %i\n",B+1);
  134. inicio = nodo_b;
  135. buscar = A;
  136. }
  137. i = 0;
  138. //printf("Nodos: ");
  139. while(i < inicio->total && !r) {
  140. //printf("%i\t ",inicio->relations[i]+1);
  141. busqueda = buscar_nodo_arbol(inicio->arbol,buscar);
  142. if(busqueda) {
  143. r = true;
  144. }
  145. i++;
  146. }
  147. //printf("\n");
  148. if(!r) {
  149. i = 0;
  150. while(i < inicio->total && !r) {
  151. pivote = todos[inicio->relations[i]];
  152. j = 0;
  153. //printf("Nodos de %i:  ",inicio->relations[i]+1);
  154. while(j < pivote->total && !r) {
  155. busqueda = buscar_nodo_arbol(pivote->arbol,buscar);
  156. //printf("%i\t ",pivote->relations[j]+1);
  157. if(busqueda) {
  158. r = true;
  159. }
  160. j++;
  161. }
  162. //printf("\n");
  163. i++;
  164. }
  165. }
  166. return r;
  167. }
  168.  
  169.  
  170. struct nodo_arbol *crear_nodo_arbol(struct nodo_arbol *padre,int valor) {
  171. struct nodo_arbol *n = calloc(sizeof(struct nodo_arbol),1);
  172. if(n == NULL) {
  173. printf("Error de Memoria\n");
  174. exit(0);
  175. }
  176. n->padre = padre;
  177. n->valor = valor;
  178. return n;
  179. }
  180.  
  181. struct nodo_arbol *agregar_valor_arbol(struct nodo_arbol *arbol,int valor) {
  182. struct nodo_arbol *temp,*pivote;
  183. int derecho = 0;
  184. if(arbol) {
  185. temp =arbol;
  186. while(temp != NULL) {
  187. pivote = temp;
  188. if(valor > temp->valor) {
  189. temp = temp->derecho;
  190. derecho = 1;
  191. }
  192. else {
  193. temp = temp->izquierdo;
  194. derecho = 0;
  195. }
  196. }
  197. temp = crear_nodo_arbol(pivote,valor);
  198. if(derecho) {
  199. pivote->derecho = temp;
  200. }
  201. else {
  202. pivote->izquierdo = temp;
  203. }
  204. return arbol;
  205. }
  206. else {
  207. temp = crear_nodo_arbol(NULL,valor);
  208. return temp;
  209. }
  210. }
  211.  
  212. struct nodo_arbol *buscar_nodo_arbol(struct nodo_arbol *arbol,int valorAbuscar) {
  213. struct nodo_arbol *temp = NULL,*pivote = NULL;
  214. int entrar = 1;
  215. temp =arbol;
  216. while(entrar == 1  && temp != NULL) {
  217. pivote = temp;
  218. if(valorAbuscar == temp->valor){
  219. entrar = 0;
  220. }
  221. else {
  222. if(valorAbuscar > temp->valor) {
  223. temp = temp->derecho;
  224. }
  225. else {
  226. temp = temp->izquierdo;
  227. }
  228. }
  229. }
  230. return temp;
  231. }

Solo habria que extenderla para que revise todos los nodos.

Saludoa
« Última modificación: 27 Julio 2016, 22:15 pm por AlbertoBSD » En línea

engel lex
Moderador Global
***
Desconectado Desconectado

Mensajes: 15.514



Ver Perfil
Re: Propuestas para resolver en C++
« Respuesta #5 en: 27 Julio 2016, 23:37 pm »

El titulo debe ser Descriptivo, te explico

Citar
Propuestas para resolver problema en C++


Describe tanto el tema como

Citar
Necesito tu ayuda para resolver un problema en C++

Es decir, no lo describe...
Citar
Describir
verbo transitivo
1.
Explicar cómo es una cosa, una persona o un lugar para ofrecer una imagen o una idea completa de ellos.
"en el manual se describen las principales especies animales que habitan en la zona; entonces aquella ciudad me pareció triste así la recuerdo y así la describo e impregnada de singular melancolía"
En línea

El problema con la sociedad actualmente radica en que todos creen que tienen el derecho de tener una opinión, y que esa opinión sea validada por todos, cuando lo correcto es que todos tengan derecho a una opinión, siempre y cuando esa opinión pueda ser ignorada, cuestionada, e incluso ser sujeta a burla, particularmente cuando no tiene sentido alguno.
AlbertoBSD
Programador y
Moderador Global
***
Desconectado Desconectado

Mensajes: 3.696


🏴 Libertad!!!!!


Ver Perfil WWW
Re: Propuestas para resolver problema en C++
« Respuesta #6 en: 27 Julio 2016, 23:47 pm »

Titulos sugeridos:

Código:
¿Mejor algoritmo? Problema con aproximaciones de Grafos

Código:
Optimizar algoritmo para busqueda de elementos

Saludos
En línea

KINGARZA

Desconectado Desconectado

Mensajes: 33

Facebook: Luis Garza


Ver Perfil
Re: Propuestas para resolver problema en C++
« Respuesta #7 en: 28 Julio 2016, 01:09 am »

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:
Código
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.                            /*DECLARO TODO LO QUE USARE DE SET Y EL VECTOR QUE GUARDARA LAS RESPUESTAS*/
  4. typedef struct arrays{
  5.    set<int>amigos;
  6. }ar;
  7.     set<int>::iterator j;
  8.     set<int>::iterator k;
  9.     vector<string>respuestas;
  10.  
  11. int main(){
  12.    cin.tie(0);
  13.    ios_base::sync_with_stdio(0);
  14.    bool encontrado;
  15.    char opcion;
  16.    int personas, comandos, a, b;
  17.    int i, l, z;
  18.    cin>>personas>>comandos;
  19.  
  20.    ar persona[personas + 1]; /*CREAMOS UN ARRAY DE SETS DE TAMAÑO PERSONAS*/
  21.  
  22.    for(i = 0; i < comandos; i++){
  23.        cin>>opcion>>a>>b;
  24.        if(opcion == 'S'){
  25.            persona[a].amigos.insert(b);
  26.            persona[b].amigos.insert(a);
  27.            for(j = persona[a].amigos.begin(); j != persona[a].amigos.end(); j++){ /* PERSONA A*/
  28.                for(k = persona[a].amigos.begin(); k != persona[a].amigos.end(); k++){
  29.                    persona[*j].amigos.insert(*k);
  30.                }
  31.            }
  32.            for(j = persona[b].amigos.begin(); j != persona[b].amigos.end(); j++){ /*PERSONA B*/
  33.                for(k = persona[b].amigos.begin(); k != persona[b].amigos.end(); k++){
  34.                    persona[*j].amigos.insert(*k);
  35.                }
  36.            }
  37.        }
  38.        else{
  39.            if(persona[a].amigos.empty() || persona[b].amigos.empty())
  40.                respuestas.push_back("0\n");
  41.            else{
  42.                encontrado = false;
  43.                for(j = persona[a].amigos.begin(); j != persona[a].amigos.end(); j++){/*BUSCAMOS SI EN LOS AMIGOS DE A ESTA B*/
  44.                    if(*j == b){
  45.                        encontrado = true;
  46.                        break;
  47.                    }
  48.                }
  49.                if(encontrado)
  50.                    respuestas.push_back("1\n");
  51.                else
  52.                    respuestas.push_back("0\n");
  53.            }
  54.        }
  55.    }
  56.    for(i = 0; i < respuestas.size(); i++)
  57.        cout<<respuestas[i];
  58.    return 0;
  59. }
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.
« Última modificación: 28 Julio 2016, 01:23 am por KINGARZA » En línea

AlbertoBSD
Programador y
Moderador Global
***
Desconectado Desconectado

Mensajes: 3.696


🏴 Libertad!!!!!


Ver Perfil WWW
Re: ¿Mejor algoritmo? Problema con aproximaciones de Grafos
« Respuesta #8 en: 28 Julio 2016, 01:40 am »

Hola.

Citar
pensaba en una búsqueda binario aunque según yo que no es posible.

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





Saludos
« Última modificación: 28 Julio 2016, 01:43 am por AlbertoBSD » En línea

KINGARZA

Desconectado Desconectado

Mensajes: 33

Facebook: Luis Garza


Ver Perfil
Re: ¿Mejor algoritmo? Problema con aproximaciones de Grafos
« Respuesta #9 en: 28 Julio 2016, 06:40 am »

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:
Código
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct nodoArbol {
  5. struct nodoArbol *ptrIzq;
  6. int dato;
  7. struct nodoArbol *prtDer;
  8. };
  9.  
  10. typedef struct nodoArbol NodoArbol;
  11. typedef NodoArbol *ptrNodoArbol;
  12.  
  13. void insertaNodo( ptrNodoArbol *ptrArbol, int valor ){
  14.  
  15.    if (*ptrArbol == NULL) { /*ARBOL VACIO*/
  16.        *ptrArbol = (NodoArbol*)malloc(sizeof(NodoArbol));
  17.        (*ptrArbol)->dato = valor;
  18.        (*ptrArbol)->ptrIzq = NULL;
  19.        (*ptrArbol)->prtDer = NULL;
  20.    }
  21.  
  22.    else {
  23.        /* el dato a insertar es menor que el dato en el nodo actual */
  24.        if (valor < (*ptrArbol)->dato) {
  25.            insertaNodo(&((*ptrArbol)->ptrIzq), valor);
  26.        }
  27.        else if (valor > (*ptrArbol)->dato) {
  28.            insertaNodo(&((*ptrArbol)->prtDer), valor);
  29.        }
  30.    }
  31. }
  32.  
  33. void inOrden(ptrNodoArbol ptrArbol){
  34.    if (ptrArbol != NULL) {
  35.        inOrden(ptrArbol->ptrIzq);
  36.        cout<<ptrArbol -> dato<<" ";
  37.        inOrden(ptrArbol->prtDer);
  38.    }
  39. }
  40.  
  41. void preOrden(ptrNodoArbol ptrArbol){
  42.    if (ptrArbol != NULL){
  43.        cout<<ptrArbol -> dato<<" ";
  44.        preOrden(ptrArbol->ptrIzq);
  45.        preOrden(ptrArbol->prtDer);
  46.    }
  47. }
  48.  
  49. void postOrden(ptrNodoArbol ptrArbol) {
  50.    if (ptrArbol != NULL){
  51.        postOrden(ptrArbol->ptrIzq);
  52.        postOrden(ptrArbol->prtDer);
  53.        cout<<ptrArbol -> dato<<" ";
  54.    }
  55. }
  56.  
  57. int main(){
  58.  
  59.    ptrNodoArbol ptrRaiz = NULL;
  60.    int limite,elemento;
  61.    cout<<"INTRODUCE CUANTOS ELEMENTOS TENDRA EL ARBOL: ";
  62.    cin>>limite;
  63.  
  64.    for (int i = 1; i <= limite; i++) {
  65.        cout<<"INGRESE ELEMENTO: ";
  66.        cin>>elemento;
  67.        insertaNodo(&ptrRaiz, elemento);
  68.    }
  69.  
  70.    cout<<"\nEL RECORRIDO EN PREORDEN ES:\n";
  71.    preOrden(ptrRaiz);
  72.  
  73.    cout<<"\nEL RECORRIDO EN INORDEN ES:\n";
  74.    inOrden(ptrRaiz);
  75.  
  76.    cout<<"\nEL RECORRIDO EN POSTORDEN ES:\n";
  77.    postOrden(ptrRaiz);
  78.  
  79.    return 0;
  80. }
Gracias por tu ayuda.
En línea

Páginas: [1] 2 Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Cual es el mejor algoritmo de encriptacion de truecrypt
Criptografía
AALD666 4 9,435 Último mensaje 3 Enero 2014, 03:47 am
por QuemoZem
Problema con grafos
Java
Puma93 1 1,579 Último mensaje 20 Junio 2013, 22:50 pm
por kasuki92
Un algoritmo determina mejor la relevancia de una película que crítica y público
Noticias
wolfbcn 0 1,259 Último mensaje 20 Enero 2015, 01:42 am
por wolfbcn
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines