Pointer to vector of objects loosing their value

I have a project I've been developing for my master's thesis. In this project, I have a parent class called node and some other children classes, for example, the class AND. And I also have a class called graph where nodes are stored using std::map. I came to the conclusion I don't need to use std::map. Using std::vector I would have quicker access to the nodes inside the graph.

The AND class has two vectors: one for its inputs and another for its outputs. I have two methods to add a pointer of a node to one of these two vectors.

When I changed from map to vector in the graph class, some of the pointers inside the AND nodes are losing their value.

I did some research on pointers, and it seems to me I am doing nothing wrong. I am lost here.

class node{
protected:
    unsigned int id;
public:
    virtual void pushOutput(node* param){}
    virtual void pushInput(node* param,bool param_polarity){}
}

class AND : public node{
    vector <node*> inputs;
    vector <node*> outputs;
public:
   void pushOutput(node* param) override;
   void pushInput(node* param,bool param_polarity) override;
}

void AND::pushOutput(node* param){
    this->outputs.push_back(param);
}

//AND::pushInput is omitted, but it is pretty similar to AND::pushOutput except with a bunch of ifs.

class graph {
protected:
//    map<unsigned int,AND> all_ANDS;
    vector<AND> all_ANDS;
public:
    AND* pushAnd(unsigned int index,AND AND_obj); 
    AND* findAnd(unsigned int);
}

AND* graph::pushAnd(unsigned int index, AND AND_obj){
//    std::pair<std::map<unsigned int,AND>::iterator,bool> ret;
//    ret=this->all_ANDS.insert(pair<unsigned int,AND>(index,AND_obj));
    all_ANDS.push_back(AND_obj);
    return &all_ANDS.back();
}

AND* graph::findAnd(unsigned int param){
//    return &this->all_ANDS.find(param)->second;
    return &all_ANDS[param];
}

Please notice the commented lines are the version the code used to work properly.

Using the methods to read from a file (some things were omitted):

bool polar;
AND* AND_ptr;
unsigned int rhs0;
for(int l=0;l<A;l++)
{
    and_index++;
    AND AND_obj(and_index*2);
    AND_ptr=this->pushAnd(and_index*2,AND_obj);
//reading info from file here and putting on rhs0 and polar.
    AND_ptr->pushInput(findAnd(rhs0),polar);
    findAnd(rhs0)->pushOutput(findAnd(and_index*2));
    findAny(rhs0)->printNode();
}

If I use the method graph::findAnd() to get a node address to push it inside another node's vector: inputs or outputs the address saved on these vectors point to some junk, but only after some processing time, it points to the proper place at first, as the AND::printNode() shows.

In other words, graph::findAnd() is returning an invalid pointer, although with the std::map version it was working just fine.

I am pretty sure my issue is due to some lack of knowledge on pointers. Although when I check other similar issues like this one Vector of object pointers returns odd values. My code seems ok to me.