I have a class Graph and it has a variable vector<int> distances
. My code runs for each testcase and gets minimum distance from source node and prints them via getDistances()
function. My problem is that the results of the first testcase are repeating for every consecutive testcases. So while looking at my code, I changed...,
while (cases--)
{
int nodes, edges;
cin>>nodes>>edges;
Graph g = Graph(nodes, true);
while(edges--)
{
int source, destination;
cin>>source>>destination;
g.connect(source, destination);
}
breadth(g);computes distances and stores by Graph class member function g.set() and g.get()
g.getDistances();//Prints distances computed in breadth() function
}
to
while (cases--)
{
int nodes, edges;
cin>>nodes>>edges;
Graph* g = new Graph(nodes, true);
while(edges--)
{
int source, destination;
cin>>source>>destination;
g->connect(source, destination);
}
breadth(g);//computes distances and stores by Graph class member function g->set() and g->get()
g->getDistances();//Prints distances computed in breadth() function
}
i.e, I changed the object to pointer object. And then the values were not redundant. I want to know why this kind of behaviour exists..why when I change the object to pointer the values were not redundant.
Before changing the object output 0 2147483647 2147483647 (Output of first testcase) 0 2147483647 2147483647 (redundant) 0 2147483647 2147483647 (redundant)
After changing to pointer object correct answers 0 2147483647 2147483647 0 1 2147483647 0 1 2
My class Graph
class Graph
{
private:
int vertices;
bool un_directed = true;
vector<vector<int>> adjList;
vector<int> distances;
public:
Graph(int vertices,bool un_directed)
{
this->vertices = vertices;
this->un_directed = un_directed;
adjList = vector<vector<int>>(vertices, vector<int>());
distances = vector<int>(vertices, INT_MAX);
setSource(0);
}
int getVertices()
{
return vertices;
}
void connect(int source, int destination)
{
cout<<"Connecting "<<source<<" and "<<destination<<endl;
adjList[source].push_back(destination);
if(un_directed) adjList[destination].push_back(source);
}
vector<int> getNeighbors(int source)
{
vector<int> result;
for(int i:adjList[source])
{
result.push_back(i);
}
return result;
}
void setSource(int source)
{
distances[source] = 0;
}
void getDistances()
{
for(int i : distances) cout<<i<<" ";
cout<<endl;
}
int getDistances(int n)
{
return distances[n];
}
void setDistance(int index, int val)
{
distances[index] = val;
}
};
Aucun commentaire:
Enregistrer un commentaire