Academic Integrity: tutoring, explanations, and feedback — we don’t complete graded work or submit on a student’s behalf.

For this project you must write a program to determine whether or not a proposed

ID: 3534400 • Letter: F

Question

For this project you must write a program to determine whether or not a

proposed set of direct computer-to-computer communication links will result in a connected

network. Assuming that communication links are bidirectional, the network can naturally be

represented as an undirected graph in which nodes are the computers and edges are the

direct communication links between them. read the description of the network from the standard input. The

description starts with a line containing the number n of nodes and the number m of links in

the network, where n and m are non-negative integers. The following m lines contain pairs

of integers between 1 and n, corresponding to the m links in the network. You must print to the standard output a new line

terminated line containing the message "connected" if the input network is connected, and "not connected" if the input network is

Explanation / Answer

#include <iostream>

#include <vector>

#include <stack>

using namespace std;


bool DFS(vector<vector<int> > &Graph)

{

vector<bool> visited(Graph.size(),false);

stack<int> S;

S.push(1);

while(!S.empty())

{

int currNode = S.top();

visited[currNode] = true;

int nextNode = 0;

for(int i=0; i<Graph[currNode].size();i++)

{

if(!visited[Graph[currNode][i]])

{

nextNode = Graph[currNode][i];

break;

}

}

if(nextNode != 0)

{

S.push(nextNode);

}

else

{

S.pop();

}

}

for(int i=1;i<visited.size();i++)

{

if (!visited[i])

return false;

}

return true;

}


int main()

{

int n,m;

cout<<"Enter number of nodes : ";

cin>>n;

vector<vector<int> > Graph(n+1);

cout<<"Enter number of links :";

cin>>m;

cout<<"Enter all the links :"<<endl;

for(int i=0;i<m;i++)

{

//cout<<i<<endl;

int a,b;

cin>>a>>b;

Graph[a].push_back(b);

Graph[b].push_back(a);

}

//cout<<"aaa";

if(DFS(Graph))

cout<<"Connected"<<endl;

else

cout<<"Not Connected"<<endl;

}

Hire Me For All Your Tutoring Needs
Integrity-first tutoring: clear explanations, guidance, and feedback.
Drop an Email at
drjack9650@gmail.com
Chat Now And Get Quote