Skip to content

Commit 0bddc6d

Browse files
amangit1314amangit1314
committed
#Modification 91
1 parent 223c856 commit 0bddc6d

4 files changed

Lines changed: 229 additions & 1 deletion

File tree

‎README.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
# Java Placement Preparation DSA CRACKER SHEET 💻🦸‍♂️🐱‍👤[181/450]
1+
# Java Placement Preparation DSA CRACKER SHEET 💻🦸‍♂️🐱‍👤[183/450]
22

33
☄ This is a full fled-ged repository for learning Java Language & DSA for Placement Preparation.
44

‎graphs/Graph_Problem_04_1.java‎

Lines changed: 92 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,92 @@
1+
package graphs;
2+
3+
// Problem Title => Java program to check if there is a cycle in directed graph using BFS.
4+
5+
import java.util.*;
6+
import java.util.Vector;
7+
8+
public class Graph_Problem_04_1 {
9+
10+
// Class to represent a graph
11+
static class Graph {
12+
// No. of vertices.
13+
int V;
14+
15+
// Pointer to an array containing adjacency list
16+
Vector<Integer>[] adj;
17+
18+
// Constructor
19+
Graph(int V) {
20+
this.V = V;
21+
this.adj = new Vector[V];
22+
for (int i = 0; i < V; i++)
23+
adj[i] = new Vector<>();
24+
}
25+
26+
// function to add an edge to graph
27+
void addEdge(int u, int v) {
28+
adj[u].add(v);
29+
}
30+
31+
// Returns true if there is a cycle in the graph else false.
32+
// This function returns true if there is a cycle in directed graph, else returns false.
33+
boolean isCycle() {
34+
35+
// Create a vector to store in degrees of all vertices. Initialize all in degrees as 0.
36+
int[] in_degree = new int[this.V];
37+
Arrays.fill(in_degree, 0);
38+
39+
// Traverse adjacency lists to fill in degrees of vertices. This step takes O(V+E) time
40+
for (int u = 0; u < V; u++) {
41+
for (int v : adj[u])
42+
in_degree[v]++;
43+
}
44+
45+
// Create a queue and enqueue all vertices with in degree 0
46+
Queue<Integer> q = new LinkedList<>();
47+
for (int i = 0; i < V; i++)
48+
if (in_degree[i] == 0)
49+
q.add(i);
50+
51+
// Initialize count of visited vertices
52+
int cnt = 0;
53+
54+
// Create a vector to store result (A topological ordering of the vertices)
55+
Vector<Integer> top_order = new Vector<>();
56+
57+
// One by one dequeue vertices from queue and enqueue adjacent if in degree of adjacent becomes 0
58+
while (!q.isEmpty()) {
59+
60+
// Extract front of queue (or perform dequeue) and add it to topological order
61+
int u = q.poll();
62+
top_order.add(u);
63+
64+
// Iterate through all its neighbouring nodes of dequeued node u and decrease their in-degree by 1
65+
for (int itr : adj[u])
66+
if (--in_degree[itr] == 0)
67+
q.add(itr);
68+
cnt++;
69+
}
70+
71+
// Check if there was a cycle
72+
return cnt != this.V;
73+
}
74+
}
75+
76+
// Driver Code
77+
public static void main(String[] args) {
78+
79+
// Create a graph given in the above diagram
80+
Graph g = new Graph(6);
81+
g.addEdge(0, 1);
82+
g.addEdge(1, 2);
83+
g.addEdge(2, 0);
84+
g.addEdge(3, 4);
85+
g.addEdge(4, 5);
86+
87+
if (g.isCycle())
88+
System.out.println("Yes");
89+
else
90+
System.out.println("No");
91+
}
92+
}

‎graphs/Graph_Problem_04_ii.java‎

Lines changed: 79 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,79 @@
1+
package graphs;
2+
// Problem Title => Java program to check if there is a cycle in directed graph using DFS.
3+
4+
import java.util.ArrayList;
5+
import java.util.LinkedList;
6+
import java.util.List;
7+
8+
public class Graph_Problem_04_ii {
9+
10+
private final int V;
11+
private final List<List<Integer>> adj;
12+
13+
public Graph_Problem_04_ii(int V) {
14+
this.V = V;
15+
adj = new ArrayList<>(V);
16+
17+
for (int i = 0; i < V; i++)
18+
adj.add(new LinkedList<>());
19+
}
20+
21+
private boolean isCyclicUtil(int i, boolean[] visited, boolean[] recStack) {
22+
// Mark the current node as visited and part of recursion stack
23+
if (recStack[i])
24+
return true;
25+
26+
if (visited[i])
27+
return false;
28+
29+
visited[i] = true;
30+
31+
recStack[i] = true;
32+
List<Integer> children = adj.get(i);
33+
34+
for (Integer c: children)
35+
if (isCyclicUtil(c, visited, recStack))
36+
return true;
37+
38+
recStack[i] = false;
39+
return false;
40+
}
41+
42+
private void addEdge(int source, int dest) {
43+
adj.get(source).add(dest);
44+
}
45+
46+
// Returns true if the graph contains a cycle, else false.
47+
// This function is a variation of DFS() in
48+
private boolean isCyclic() {
49+
50+
// Mark all the vertices as not visited and not part of recursion stack
51+
boolean[] visited = new boolean[V];
52+
boolean[] recStack = new boolean[V];
53+
54+
55+
// Call the recursive helper function to detect cycle in different DFS trees
56+
for (int i = 0; i < V; i++)
57+
if (isCyclicUtil(i, visited, recStack))
58+
return true;
59+
60+
return false;
61+
}
62+
63+
// Driver code
64+
public static void main(String[] args) {
65+
Graph_Problem_04_ii graph = new Graph_Problem_04_ii(4);
66+
67+
graph.addEdge(0, 1);
68+
graph.addEdge(0, 2);
69+
graph.addEdge(1, 2);
70+
graph.addEdge(2, 0);
71+
graph.addEdge(2, 3);
72+
graph.addEdge(3, 3);
73+
74+
if(graph.isCyclic())
75+
System.out.println("Graph contains cycle");
76+
else
77+
System.out.println("Graph doesn't " + "contain cycle");
78+
}
79+
}

‎heap/Problem_07.java‎

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
package heap;
2+
// Problem Title => Merge Two Binary Max Heaps.
3+
public class Problem_07 {
4+
5+
// Standard heapify function to heapify a subtree rooted under idx.
6+
// It assumes that subtrees of node are already heapified.
7+
public static void maxHeapify(int[] arr, int n, int i){
8+
9+
// Find largest of node and its children
10+
if(i >= n)
11+
return;
12+
13+
int l = i*2 + 1;
14+
int r = i*2 + 2;
15+
int max;
16+
17+
if(l < n && arr[l] > arr[i])
18+
max = l;
19+
20+
else max = i;
21+
22+
if (r < n && arr[r] > arr[max]) {
23+
max = r;
24+
}
25+
26+
// Put maximum value at root and recur for the child with the maximum value
27+
if (max != i) {
28+
int temp = arr[max];
29+
arr[max] = arr[i];
30+
arr[i] = temp;
31+
maxHeapify(arr, n, max);
32+
}
33+
}
34+
35+
public static void mergeHeaps(int[] arr, int[] a, int[] b, int n, int m){
36+
if (n >= 0) System.arraycopy(a, 0, arr, 0, n);
37+
if (m >= 0) System.arraycopy(b, 0, arr, n, m);
38+
n = n + m;
39+
// Builds a max heap of given arr[0..n-1]
40+
for (int i = n / 2 - 1; i >= 0; i--)
41+
maxHeapify(arr, n, i);
42+
}
43+
public static void main(String[] args) {
44+
int[] a = {10, 5, 6, 2};
45+
int[] b = {12, 7, 9};
46+
int n = a.length;
47+
int m = b.length;
48+
49+
int[] merged = new int[m + n];
50+
51+
mergeHeaps(merged, a, b, n, m);
52+
53+
for (int i = 0; i < m + n; i++)
54+
System.out.print(merged[i] + " ");
55+
System.out.println();
56+
}
57+
}

0 commit comments

Comments
 (0)