0

I've got stuck with the problem of counting amount of isolated vertices in the graph. Below you will see the code

#include <iostream>
#include <vector>
#define V 4 // amount of vertices in the graph 
// Function to add edge between vertices
void addEdge(std::vector<int> adj[V], int u, int v)
{
   adj[u].push_back(v);
   adj[v].push_back(u);
}
// Function to count amount of isolated vertices in graph with return type int
int FindIsolated(std::vector<int> adj[V])
{
   int isolated = 0; // counter to save amount of isolated vertices
   for(int v = 0; v < V; ++v)
   {
      for(auto x: adj[v])
      {
         if(x == 0)
         {
            isolated++;
         }
      }
   }
    return isolated;
}
// Driver code
int main()
{
   std::vector<int> adj[V];
   addEdge(adj, 1, 2);
   addEdge(adj, 1, 3);
   addEdge(adj, 0, 0);
   std::cout << "This graph contains " << FindIsolated(adj) << " isolated vertices" << std::endl;
   std::cin.get();
   return 0;
}

In the output I have a message: "This graph contains 2 isolated vertices" but I need the message "This graph contains 1 isolated vertices" Any suggestions and describing the solution is appreciated. Thank you :)

Venom ___Manny
  • 1
  • 3
  • Currently you are counting edges that are connected to the vertex 0. What is the expected answer? – MikeCAT Jul 20 '22 at 12:36
  • The expected answer is "This graph contains 1 isolated vertices" – Venom ___Manny Jul 20 '22 at 12:41
  • 1
    @Venom___Manny *Any suggestions* -- [What is a debugger?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) – PaulMcKenzie Jul 20 '22 at 12:42
  • But input edges lead to 2 isolated graphs. Node `0` is not reachable from anything else and nodes: `1`, `2`, `3` are connected together. So basically you are expecting invalid result. Even though result is correct, the algorithm is invalid. For other inputs it will produce invalid results. – Marek R Jul 20 '22 at 12:54
  • Can you show please how to detect vertices with the degree 0 using adjacency matrix – Venom ___Manny Jul 20 '22 at 13:13
  • 1
    Before you write a single line of code, you should have had a plan on paper as to what operations will be performed and how they will be performed. Then you write your program following the plan. If there are bugs, you debug your program to see where it didn't follow the plan and fix those bugs. Or by debugging, you find out the original plan you had on paper was flawed, and you need to adjust that plan or start over with a new plan. That's how all of this should work. – PaulMcKenzie Jul 20 '22 at 13:26

1 Answers1

-1
void addEdge(std::vector<int> adj[V], int u, int v)
{
   adj[u].push_back(v);
   adj[v].push_back(u);
}

This is going to give you problems!!!! It should not even compile!!!!!!!!!!!!!!!

adj[u] is an integer, not a vector. adj[u].push_back(v); makes no sense

Normally a adjacency matrix is used for this

Like so

void addEdge(
   std::vector<std::vector<<int>>& adj,
   int u, int v)
{
   adj[u].push_back(v);
   adj[v].push_back(u);
}

@aschepler points out you are using an unusual syntax to define your matrix. Please do not do this.

This is wrong

  for(int v = 0; v < V; ++v)
   {
      for(auto x: adj[v])
      {
         if(x == 0)
         {
            isolated++;
         }
      }
   }

Should be

  for(int v = 0; v < V; ++v)
   {
      if( ! adj[v].size() )
            isolated++;
   }
ravenspoint
  • 19,093
  • 6
  • 57
  • 103
  • Notice the parameter declaration `std::vector adj[V]`, which actually has type `std::vector*`. The syntax is valid, as strange as using a raw array of vectors is. – aschepler Jul 20 '22 at 14:58