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!!!