HackerEarth Matt's Graph Book problem solution

In this HackerEarth Matt’s Graph Book problem solution Matt loves Graph Theory. He recently enrolled into the Algorithms course and started liking it too. His teacher understood his love for graphs and decided to give him a problem.

She gives him a Tree and asks him to write a program to find if it’s connected or not. She realizes that Matt would do this in no time. So, instead she gives him a Graph and then removes a vertex from it and now asks him to find if the resultant graph is connected or not.

Since he is new to programming and algorithms, you have to help him solve this problem.

HackerEarth Matt’s Graph Book problem solution.

#include<bits/stdc++.h>

using namespace std;

class Graph
{
        int V;
        vector<int> *adj;
        void DFSUtil(int v, bool visited[]);
        int count;
    public:
        Graph(int V);
        void addEdge(int v, int w);
        void removeNode(int v);
        void DFS(int v);
        int getCount();
};

Graph::Graph(int V)
{
    this->V = V;
    adj = new vector<int>[V];
    count = 0;
}

int Graph::getCount(){
    return count;
}

void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w);
    adj[w].push_back(v);
}

void Graph::removeNode(int v)
{
    for(int i=0; i<V; i++){
        for(int j=0; j<adj[i].size();j++){
            if(i == v || adj[i][j] == v){
                adj[i][j] = -1;
            }
        }
    }
}

void Graph::DFSUtil(int v, bool visited[])
{

    visited[v] = true;
    count++;


    vector<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
        if (!visited[*i] && *i != -1)
            DFSUtil(*i, visited);
}


void Graph::DFS(int v)
{

    bool *visited = new bool[V];
    for (int i = 0; i < V; i++)
        visited[i] = false;


    DFSUtil(v, visited);
}

int main()
{
    int N;
    cin>>N;
    Graph g(N);

    int noOfEdge;
    cin>>noOfEdge;
    for(int i=0 ;i<noOfEdge;i++){
        int a,b;
        cin>>a>>b;
        g.addEdge(a,b);
    }
    int nodeToBeRemoved;
    cin>>nodeToBeRemoved;
    g.removeNode(nodeToBeRemoved);

    if(nodeToBeRemoved - 1 < 0){
        g.DFS(nodeToBeRemoved+1);
    }
    else{
        g.DFS(nodeToBeRemoved - 1);
    }
    int kount = g.getCount();
    if(kount == N-1)    cout<<"Connected"<<endl;
    else    cout<<"Not Connected"<<endl;
}

Second solution

#include <bits/stdc++.h>
using namespace std;
struct linklist
{
  struct graph *node;
  struct linklist *next;
};

struct graph
{
  int data;
  struct linklist *head;
};

map<int,graph *> mp;
map<int,bool> flag;

void bfs(graph *root)
{
  int i=1;
  queue<graph *> q;
  q.push(root);
  while(!q.empty())
  {
    graph *temp1=q.front();
    q.pop();
    //cout<<temp1->data<<": ";
    if(flag[temp1->data]==false)
    {
      linklist *temp=temp1->head;
      while(temp!=NULL)
      {
        if(flag[temp->node->data]==false)
        {
          //cout<<temp->node->data<<" ";
          q.push(temp->node);
        }
        temp=temp->next;
      }
      flag[temp1->data]=true;
    }
    //cout<<endl;
  }
}

int main()
{
  int n;
  cin>>n;
  assert(1<=n && n<=100000);
  int k;
  cin>>k;
  assert(1<=k && k<=200000);
  //k--;
  int x[k],y[k];
  for(int i=0;i<k;i++)
  {
    cin>>x[i]>>y[i];
    assert(0<=x[i] && x[i]<=100000);
    assert(0<=y[i] && y[i]<=100000);
  }
  int remver;
  cin>>remver;
  graph *root;
  for(int i=0;i<k;i++)
  {
    //cout<<x[i]<<y[i]<<endl;
    if(x[i]!=remver)
    {
      if(mp.find(x[i])==mp.end())
      {
        mp[x[i]]=new graph();
        mp[x[i]]->data=x[i];
        mp[x[i]]->head=NULL;
        flag[x[i]]=false;
      }
      root=mp[x[i]];
    }
    if(y[i]!=remver)
    {
      if(mp.find(y[i])==mp.end())
      {
        mp[y[i]]=new graph();
        mp[y[i]]->data=y[i];
        mp[y[i]]->head=NULL;
        flag[y[i]]=false;
      }
    }
    if(x[i]!=remver && y[i]!=remver)
    {
      linklist *temp=mp[x[i]]->head;
      if(temp==NULL)
      {
        mp[x[i]]->head=new linklist();
        mp[x[i]]->head->node=mp[y[i]];
        mp[x[i]]->head->next=NULL;
      }
      else
      {
        while(temp->next!=NULL)
          temp=temp->next;
        temp->next=new linklist();
        temp->next->node=mp[y[i]];
        temp->next->next=NULL;
      }
      swap(x[i],y[i]);
      temp=mp[x[i]]->head;
      if(temp==NULL)
      {
        mp[x[i]]->head=new linklist();
        mp[x[i]]->head->node=mp[y[i]];
        mp[x[i]]->head->next=NULL;
      }
      else
      {
        while(temp->next!=NULL)
          temp=temp->next;
        temp->next=new linklist();
        temp->next->node=mp[y[i]];
        temp->next->next=NULL;
      }
    }
  }
  bfs(root);
  for(map<int,bool>::iterator it=flag.begin();it!=flag.end();++it)
  {
    if(it->second==false)
    {
      cout<<"Not Connected";
      return 0;
    }
  }
  cout<<"Connected";
  
}

coding problems solutions