0

I want to print the number of connected components in a Graph. For this, I am using bfs traversal. I have used an map to store the adjacency list. My logic is that if vis[itr]! = true then I am incrementing the count. But the count is always coming out to be zero. Why is this so? Can anyone help me out?

#include<bits/stdc++.h>
using namespace std;

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

vector<int>bfsOfGraph(int n, map<int,vector<int>>adj, int &count)
{
    vector<int>vis(n,0);
    vis[0]=1;
    queue<int>q;
    q.push(0);
    vector<int>bfs;   
    while(!q.empty())
    {
        auto node= q.front();
        q.pop();
        bfs.push_back(node);
        
        for(auto it: adj[node])
        {
            if(!vis[it]){
                count++;
                vis[it]=1;0.
                q.push(it);
            }
        }
    }
    cout<<"\n"<<count<<"\n";
    return bfs;
}

void printGraph(int n, map<int,vector<int>>adj)
{
    for(auto i : adj)
    {
        cout<<i.first<<" -> ";
        for(auto j:i.second)
        {
            cout<<j<<" ";
        }
        cout<<"\n";
    }
}


int main()
{
    int n,e;
    cout<<"Enter number of nodes : ";
    cin>>n;
    cout<<"\nEnter number of edges : ";
    cin>>e;
    cout<<"\nAdd edges :\n";
    map<int,vector<int>>adj;
    for(int i=0;i<e;i++)
    {
        int u,v;
        cin>>u>>v;
        addEdge(adj,u,v);
    }
    cout<<"\nPrinting Graph \n";
    printGraph(n,adj);
    int count=0;
    bfsOfGraph(n,adj,count);
    cout<<"\n"<<count;
    return 0;
}
Anurag Kumar Singh
  • 13
  • 3
  • How about trying to build (with extra warnings enabled, treated as errors) on your own system, and the [*debug*](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) your program? – Some programmer dude Oct 08 '22 at 08:46
  • At a quick glance, I find that if we have a single node, which does not have adjacencies, we have zero iterations of the for loop, and thus the counter is not increased. If I got this right, it already fails at the simplest example, and you should rethink your algorithm. – Aziuth Oct 08 '22 at 08:53
  • Also, in general, if you start at one node and then do BFS, and you only ever add nodes which are connected to the first node, then how should it ever reach a second connected component? Lacks an iteration over all nodes. – Aziuth Oct 08 '22 at 08:55
  • On a couple of other notes: [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h), [Why is "using namespace std;" considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) And so-called "competition" and "judge" sites are *not* supposed to be used as any kind of learning or teaching resource. – Some programmer dude Oct 08 '22 at 13:24

0 Answers0