#include <iostream> #include <vector> #include <stack> using namespace std; bool
ID: 3534432 • Letter: #
Question
#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;
}
Explanation / Answer
public class GlobalMembersGraph
{
public static boolean DFS(java.util.ArrayList<java.util.ArrayList<Integer>> Graph)
{
java.util.ArrayList<Boolean> visited = new java.util.ArrayList<Boolean>(Graph.size(),false);
java.util.Stack<Integer> S = new java.util.Stack<Integer>();
S.push(1);
while (!S.empty())
{
int currNode = S.peek();
visited.set(currNode, true);
int nextNode = 0;
for (int i = 0; i < Graph.get(currNode).size();i++)
{
if (!visited.get(Graph.get(currNode).get(i)))
{
nextNode = Graph.get(currNode).get(i);
break;
}
}
if (nextNode != 0)
{
S.push(nextNode);
}
else
{
S.pop();
}
}
for (int i = 1;i < visited.size();i++)
{
if (!visited.get(i))
return false;
}
return true;
}
public static int Main()
{
int n;
int m;
System.out.print("Enter number of nodes : ");
cin >> n;
java.util.ArrayList<java.util.ArrayList<Integer>> Graph = new java.util.ArrayList<java.util.ArrayList<Integer>>(n + 1);
System.out.print("Enter number of links :");
cin >> m;
System.out.print("Enter all the links :");
System.out.print(" ");
for (int i = 0;i < m;i++)
{
//cout<<i<<endl;
int a;
int b;
cin >> a >> b;
Graph.get(a).add(b);
Graph.get(b).add(a);
}
//cout<<"aaa";
if (GlobalMembersGraph.DFS(Graph))
{
System.out.print("Connected");
System.out.print(" ");
}
else
{
System.out.print("Not Connected");
System.out.print(" ");
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.