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;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.