1. Which of the following is not a fundamental type is not present in C but present in C++?
bool
2. The topological sorting of any DAG can be done in ____ time.
linear
3. Which of the following is not a topological sorting of the given graph?
A B C D F E
5. Which of the following is an entry-controlled loop?
for
4. What is the maximum number of edges present in a simple directed graph with 7 vertices if there exist no cycles in the graph?
6
6. Question 6 + 1 - 0 What will be the outcome of the below program?
public class MainClass { double overloadedMethod(double d) { return d *= d; } int overloadedMethod(int i) { return overloadedMethod(i *= i); } float overloadedMethod(float f) { return overloadedMethod(f *= f); } public static void main(String[] args) { MainClass main = new MainClass(); System.out.println(main.overloadedMethod(100)); } }
Compilation Error
7. With V(greater than 1) vertices, how many edges at most can a Directed Acyclic Graph possess?
(V*(V-1))/2
8. Which of the following is an exit-controlled loop?
do-while
9. Predict the output: final class Base
{ public void m1(){ System.out.println("Final class()"); } } class Derived extends Base { public void m2(){ System.out.println("Extended class"); } } public class Program { public static void main(String[] args) { Derived d = new Derived(); d.m2(); } }
Extended Class
10. What would be the DFS traversal of the given Graph?
ABCED
***************************************************************************
PROGRAMMING
1.
Problem Statement Given a Directed Graph with V vertices (Numbered from 0 to V-1) and E edges, check whether it contains any cycle or not. Input Format First line of input contains two integers n and e,where n represents the number of nodes and e represents the number of edges. Each of next e lines contains two integers u and v, where u represents the starting node and v represents the ending node. 0 is the starting vertex in each test case. Constraints 1 ≤ V, E ≤ 10^5 Output Format Print "1" (without sub quotes) if the graph contains cycle else print "0".
C++ Code:
#include<bits/stdc++.h>
using namespace std;
class Graph
{
int V;
list<int> *adj;
bool isCyclicUtil(int v, bool visited[], bool *rs);
public:
Graph(int V); // Constructor
void addEdge(int v, int w); // to add an edge to graph
bool isCyclic(); // returns true if there is a cycle in this graph
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}
// This function is a variation of DFSUtil() in https://www.geeksforgeeks.org/archives/18212
bool Graph::isCyclicUtil(int v, bool visited[], bool *recStack)
{
if(visited[v] == false)
{
// Mark the current node as visited and part of recursion stack
visited[v] = true;
recStack[v] = true;
// Recur for all the vertices adjacent to this vertex
list<int>::iterator i;
for(i = adj[v].begin(); i != adj[v].end(); ++i)
{
if ( !visited[*i] && isCyclicUtil(*i, visited, recStack) )
return true;
else if (recStack[*i])
return true;
}
}
recStack[v] = false; // remove the vertex from recursion stack
return false;
}
// Returns true if the graph contains a cycle, else false.
// This function is a variation of DFS() in https://www.geeksforgeeks.org/archives/18212
bool Graph::isCyclic()
{
// Mark all the vertices as not visited and not part of recursion
// stack
bool *visited = new bool[V];
bool *recStack = new bool[V];
for(int i = 0; i < V; i++)
{
visited[i] = false;
recStack[i] = false;
}
// Call the recursive helper function to detect cycle in different
// DFS trees
for(int i = 0; i < V; i++)
if (isCyclicUtil(i, visited, recStack))
return true;
return false;
}
int main()
{
int n,e;
cin>>n>>e;
Graph g(n);
int a[n],b[e];
for(int i=0;i<e;i++)
{
cin>>a[i]>>b[i];
g.addEdge(a[i],b[i]);
}
if(g.isCyclic())
cout << "1";
else
cout << "0";
return 0;
}
2. Problem Statement Given a connected undirected graph. Perform a Depth First Traversal of the graph. Note: Use recursive approach to find the DFS traversal of the graph starting from the 0th vertex from left to right according to the graph.. Input Format First line of input contains two integers n and e, where n represents the number of nodes and e represents the number of edges. Each of next e lines contains two integers u and v, where u represents the starting node and v represents the ending node and vice-versa(since the graph is undirected) 0 is the starting vertex in each test case. Constraints 1 ≤ V, E ≤ 10^4 Output Format Print the DFS traversal of the graph.
Python Code:
class Solution:
def dfsOfGraph(self, V, adj):
def dfs(node, visited, ans):
visited[node] = 1
ans.append(node)
for i in adj[node]:
if not visited[i]:
dfs(i, visited, ans)
ans = []
visited = [0]*V
dfs(0, visited, ans)
return ans
if __name__ == '__main__':
V, E = map(int, input().split())
adj = [[] for i in range(V)]
for _ in range(E):
u, v = map(int, input().split())
adj[u].append(v)
adj[v].append(u)
ob = Solution()
ans = ob.dfsOfGraph(V, adj)
for i in range(len(ans)):
print(ans[i], end = " ")
print()
3. Problem Statement Given a directed graph. The task is to do Breadth First Traversal of this graph starting from 0. Note: One can move from node u to node v only if there's an edge from u to v and find the BFS traversal of the graph starting from the 0th vertex, from left to right according to the graph. Also, you should only take nodes directly or indirectly connected from Node 0 in consideration. Input Format First line of input contains two integers n and e, where n represents the number of nodes and e represents the number of edges. Each of next e lines contains two integers u and v, where u represents the starting node and v represents the ending node. 0 is the starting vertex in each test case. Constraints 1 ≤ V, E ≤ 104 Output Format Print the BFS traversal of the graph
C++ code:
#include<bits/stdc++.h>
using namespace std;
class Solution
{
public:
vector<int>bfsOfGraph(int V, vector<int> adj[])
{
vector<bool> visited(V,false);
queue<int> q;
vector<int> ans;
q.push(0);
visited[0]=true;
while(!q.empty())
{
int x=q.front();
q.pop();
ans.push_back(x);
for(int v:adj[x])
{
if(visited[v]!=true)
{
q.push(v);
visited[v]=true;
}
}
}
return ans;
}
};
int main()
{
int V, E;
cin >> V >> E;
vector<int> adj[V];
for(int i = 0; i < E; i++)
{
int u, v;
cin >> u >> v;
adj[u].push_back(v);
}
Solution obj;
vector<int>ans=obj.bfsOfGraph(V, adj);
for(int i=0;i<ans.size();i++){
}
return 0;
}
Post a Comment