Graphs.txt

SOLUTIONS OF THESE QUESTIONS ARE EITHER ON GFG OR ON LEETCODE.
---------------------------------------Graphs-----------------------------------------


1. Implement a Graph

public static void main(String[] args) {
		Scanner scn = new Scanner(System.in);
		int n = scn.nextInt();
		int m = scn.nextInt();

		ArrayList<ArrayList<pair>> adj = new ArrayList<>();
		for (int i = 1; i <= n + 1; i++) {
			adj.add(new ArrayList<>());
		}

		for (int i = 0; i < m; i++) {
			int u = scn.nextInt();
			int v = scn.nextInt();
			int w = scn.nextInt();

			pair p1 = new pair(v, w);
			adj.get(u).add(p1);

			pair p2 = new pair(u, w);
			adj.get(v).add(p2);
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 0; j < adj.get(i).size(); j++) {
				System.out.println(i + " -> " + adj.get(i).get(j).node + " - " + adj.get(i).get(j).weight);
			}
		}
	}

	public static class pair {
		int node;
		int weight;

		pair(int n, int w) {
			this.node = n;
			this.weight = w;
		}

	}
--------------------------------------------------------------------------------------
2. BFS of a Graph
// T-> O(N+E)
// S-> O(N)+O(N)+O(N+E)
// visArray, queue, adj list
	public static ArrayList<Integer> BfsOfGraph(int v, ArrayList<ArrayList<Integer>> adj) {

		ArrayList<Integer> bfs = new ArrayList<>();
		boolean[] vis = new boolean[v + 1]; // taken this so that we traverse through all connected components in case
											// of disconnected graph

		for (int i = 1; i <= v; i++) {
			if (!vis[i]) {
				Queue<Integer> q = new LinkedList<>();

				q.add(i);
				vis[i] = true;
				while (!q.isEmpty()) {
					int r = q.poll();
					bfs.add(r);

					for (int an : adj.get(r)) {
						if (!vis[an]) {
							vis[an] = true;
							q.add(an);
						}
					}
				}
			}
		}
		return bfs;
	}
--------------------------------------------------------------------------------------
3. DFS of a Graph

// T-> O(N+E)
// S-> O(N)+O(N)+O(N+E)

	// for dfs either you can copy same code for bfs and instead of using queue use
	// stack OR you can apply recursion

	public static ArrayList<Integer> DfsOfGraph(int v, ArrayList<ArrayList<Integer>> adj) {
		ArrayList<Integer> storeDfs = new ArrayList<>();
		boolean[] vis = new boolean[v + 1];
		for (int i = 1; i <= v; i++) {
			if (!vis[i]) {
				dfs(i, vis, adj, storeDfs);
			}
		}
		return storeDfs;
	}

	public static void dfs(int node, boolean[] vis, ArrayList<ArrayList<Integer>> adj, ArrayList<Integer> storeDfs) {
		storeDfs.add(node);
		vis[node]=true;
		for(int an:adj.get(node)) {
			if(!vis[an]) {
				dfs(an, vis, adj, storeDfs);
			}
		}
	}
--------------------------------------------------------------------------------------
3. Cycle Detection in Undirected Graph

//For DFS & BFS
// T-> O(N+E)
// S-> O(N)+O(N)+O(N+E)

Using BFS->
	public static boolean CycleDetectionBFS(int v, ArrayList<ArrayList<Integer>> adj) {
		boolean vis[] = new boolean[v + 1];

		for (int i = 1; i <= v; i++) {
			if (!vis[i]) {
				if (checkCycleBfs(i, adj, vis)) {
					return true;
				}
			}
		}
		return false;
	}

	private static boolean checkCycleBfs(int s, ArrayList<ArrayList<Integer>> adj, boolean[] vis) {
		Queue<Node> q = new LinkedList<>();
		vis[s] = true;
		q.add(new Node(s, -1));

		while (!q.isEmpty()) {
			int n = q.peek().node;
			int p = q.peek().parent;
			q.remove();
			for (int an : adj.get(n)) { // an->adjNodes of curr node
				if (!vis[an]) {
					vis[an] = true;
					q.add(new Node(an, n));
				} else if (p != an) {
					// this detects the cycle -> as this indicates that the this node(an=adjNodes)
					// is visited and it's not equal to (parent node/prev node) of curr node
					// means curr node has come from another path also at meets here therefore makes
					// cycle
					return true;
				}
			}
		}
		return false;
	}

	public static class Node {
		int node;
		int parent;

		public Node(int n, int p) {
			this.node = n;
			this.parent = p;
		}
	}

Using DFS->
public static boolean CycleDetectionDFS(int v, ArrayList<ArrayList<Integer>> adj) {

		boolean vis[] = new boolean[v + 1];

		for (int i = 1; i <= v; i++) {
			if (!vis[i]) {
				if (checkCycleDfs(i, -1, adj, vis)) {
					return true;
				}
			}
		}
		return false;
	}

	private static boolean checkCycleDfs(int node, int parent, ArrayList<ArrayList<Integer>> adj, boolean[] vis) {
		vis[node] = true;

		for (int an : adj.get(node)) {
			if (!vis[an]) {
				if (checkCycleDfs(an, node, adj, vis))
					return true;
			} else if (parent != an) {
				return true;
			}
		}
		return false;
	}
--------------------------------------------------------------------------------------
4. Cycle Detection in directed Graph

//For DFS & BFS
// T-> O(N+E)
// S-> O(N)+O(N)+O(N+E)

Using DFS->
public static boolean DetectCycleDfs(int n, ArrayList<ArrayList<Integer>> adj) {
		boolean vis[] = new boolean[n + 1];
		boolean dfsVis[] = new boolean[n + 1];

		for (int i = 1; i <= n; i++) {
			if (!vis[i]) {
				if (IsCycleDfs(i, vis, dfsVis, adj)) {
					return true;
				}
			}
		}
		return false;
	}

	public static boolean IsCycleDfs(int node, boolean[] vis, boolean[] dfsVis, ArrayList<ArrayList<Integer>> adj) {
		vis[node] = true;
		dfsVis[node] = true;
		for (int an : adj.get(node)) {
			if (!vis[an]) {
				if (IsCycleDfs(an, vis, dfsVis, adj))
					return true;
			} else if (dfsVis[an]) { // here it get checked there exists any cycle in directed graph
				return true;
			}
		}

		dfsVis[node] = false;
		return false;
	}

Using BFS->
// For Bfs we use topological sort. if we are unable to generate topological
	// sort it means the graph must have cycle because we use topoSort in DAG.
	public static boolean CycleDetectionBfs(int n, ArrayList<ArrayList<Integer>> adj) {
		int[] indegree = new int[n + 1];

		for (int i = 1; i <= n; i++) {
			for (int an : adj.get(i)) {
				indegree[an]++; // as these are adjacent of i node means there is incoming edge from i (which is
								// indegree)
			}
		}

		Queue<Integer> q = new LinkedList<>();
		for (int i = 1; i <= n; i++) {
			if (indegree[i] == 0)
				q.add(i);
		}
		int c = 0;
		while (!q.isEmpty()) {
			int rn = q.poll();
			c++;
			for (int an : adj.get(rn)) {
				indegree[an]--;
				if (indegree[an] == 0) {
					q.add(an);
				}
			}
		}
		if (c == n)
			return false; // because topoSort is linear ordering there at most total n nodes will be
							// encountered.
		return true; // if not means there must be cycle
	}
--------------------------------------------------------------------------------------
5. Topological Sorting of Graph

// Topological Sorting->It is linear ordering of vertices such that if there is
	// an edge u->v, u appears before v in that ordering.
	// there can be multiple topoSort for a given graph. Topological sorting is
	// possible for Directed Acyclic Graphs (DAG)

//	For DFS Intuition
	// The general intuition behind this algo is-> just because if there is a
	// path/edge from u->v the dfs call went from u to v so, the first dfs call that
	// will
	// get over will be of v after that of u, so automatically if your stack is the
	// topoSort, v will be inserted First right after will u, which is making sure
	// that if there is an edge from u to v , u appears before v.

	// T-> O(N+E)
	// S-> vis->O(N) + auxiliary space (recursion)->O(N) + ajdList->O(N+E)
	// +TopoSortSTACK->O(N)

Using Dfs->

public static ArrayList<Integer> TopoSortDfs(int n, ArrayList<ArrayList<Integer>> adj) {
		Stack<Integer> st = new Stack<>();
		boolean[] vis = new boolean[n + 1];

		for (int i = 1; i <= n; i++) {
			if (!vis[i]) {
				Dfs(i, vis, st, adj);
			}
		}

		ArrayList<Integer> Topo = new ArrayList<>();
		while (!st.isEmpty()) {
			Topo.add(st.pop());
		}
		return Topo;
	}

	public static void Dfs(int node, boolean[] vis, Stack<Integer> st, ArrayList<ArrayList<Integer>> adj) {
		vis[node] = true;
		for (int an : adj.get(node)) {
			if (!vis[an])
				Dfs(an, vis, st, adj);
		}
		st.push(node);
	}

Using BFS->

	// For BFS Intuition
// if a node is appearing in the starting of Ans List then it means that there is no edge before that node that means we can say topological sort start with 
//	someone	who has indegree 0, as there can be multiple topoSort therefore it can start with any node having indegree 0, Why did we subtract indegrees of 
//	adjacent nodes ? we can say that this node has dependency factor on its adjacent nodes therefore as we write or add this node to the anslist , all the edges 
//	between its adjacent will go off so this decreases the indegree of the adjacent nodes. and now as soon as their(adj nodes) indegrees become 0 they become 
//	independent hence we can add them to the ans.	

	// Bfs Topological Sort is also known as Kahn's Algorithm
//	Time and space complexity is same as DfsTopoSort.
	public static ArrayList<Integer> TopoSortBfs(int n, ArrayList<ArrayList<Integer>> adj) {
		ArrayList<Integer> topo = new ArrayList<>();
		int[] indegree = new int[n + 1];

		for (int i = 1; i <= n; i++) {
			for (int an : adj.get(i)) {
				indegree[an]++; // as these are adjacent of i node means there is incoming edge from i (which is
								// indegree)
			}
		}

		Queue<Integer> q = new LinkedList<>();
		for (int i = 1; i <= n; i++) {
			if (indegree[i] == 0)
				q.add(i);
		}

		while (!q.isEmpty()) {
			int rn = q.poll();
			topo.add(rn);
			for (int an : adj.get(rn)) {
				indegree[an]--;
				if (indegree[an] == 0) {
					q.add(an);
				}
			}
		}
		return topo;
	}
--------------------------------------------------------------------------------------
6. Bipartite Graph

// Bipartite Graph-> A graph that can colored using exactly 2 colors such that
	// no two adjacent nodes have same color.
	// KeyObservations->
//	1. If a graph has odd length cycle, it is not bipartite
//  2. If graph doesn't have odd length cycle, then it is bipartite( covers no cycle and cycle with even length)

//	For DFS & BFS
	// T-> O(N+E)
	// S-> O(N)+O(N)+O(N+E)

Using Bfs->
public static boolean BipartiteBfs(int n, ArrayList<ArrayList<Integer>> adj) {
		int[] color = new int[n + 1];
		Arrays.fill(color, -1);
		for (int i = 1; i <= n; i++) {
			if (color[i] == -1) {
				if (!checkBipartiteBfs(i, adj, color))
					return false;
			}
		}
		return true;
	}

	public static boolean checkBipartiteBfs(int s, ArrayList<ArrayList<Integer>> adj, int[] color) {
		Queue<Integer> q = new LinkedList<>();
		q.add(s);
		color[s] = 1;

		while (!q.isEmpty()) {
			int rn = q.poll();
			for (int an : adj.get(rn)) {
				if (color[an] == -1) {
					color[an] = 1 - color[rn];
					q.add(an);
				} else if (color[an] == color[rn])
					return false;
			}

		}
		return true;
	}

Using DFS->
public static boolean BipartiteDfs(int v, ArrayList<ArrayList<Integer>> adj) {
		int[] color = new int[v + 1];
		Arrays.fill(color, -1);
		for (int i = 1; i <= v; i++) {
			if (color[i] == -1) {
				if (!checkBipartiteDfs(i, adj, color))
					return false;
			}
		}
		return true;
	}

	private static boolean checkBipartiteDfs(int node, ArrayList<ArrayList<Integer>> adj, int[] color) {
		if (color[node] == -1)
			color[node] = 1;

		for (int an : adj.get(node)) {
			if (color[an] == -1) {
				color[an] = 1 - color[node];
				if (!checkBipartiteDfs(an, adj, color))
					return false;
			} else if (color[an] == color[node])
				return false;
		}
		return true;
	}
--------------------------------------------------------------------------------------
#) SHORTEST PATHS->

// Shortest distance from source to every other node in Undirected Graph with Unit weights.
// Bfs Algorithm always gives shortest path as it moves every step by unit distance.	
//	TC->O(N+E)
//	SC->O(2N)
	public static void ShortestDistanceUndirectedGraph(int n, int src, ArrayList<ArrayList<Integer>> adj) {
		int[] dis = new int[n];
		for (int i = 0; i < n; i++) {
			dis[i] = 1000000000;
		}

		Queue<Integer> q = new LinkedList<>();
		q.add(src);
		dis[src] = 0;

		while (!q.isEmpty()) {
			int rn = q.poll();
			for (int an : adj.get(rn)) {
				if (dis[rn] + 1 < dis[an]) {
					dis[an] = dis[rn] + 1;
					q.add(an);
				}
			}
		}
		for (int i = 0; i < n; i++) {
			System.out.print(dis[i] + " ");
		}
		System.out.println();

	}

	// Shortest distance from source to every other node in Directed Acyclic Graph
	// with weights.
	public static void ShortestPathDirectedAcyclicGraph(int n, int src, ArrayList<ArrayList<pair>> adj) {
		Stack<Integer> st = new Stack<>();
		boolean[] vis = new boolean[n];

		for (int i = 0; i < n; i++) {
			if (!vis[i]) {
				TopoSortDfs(i, vis, st, adj);
			}
		}
		int[] dis = new int[n];
		for (int i = 0; i < n; i++) {
			dis[i] = Integer.MAX_VALUE;
		}
		dis[src] = 0;

		while (!st.isEmpty()) {
			int node = st.pop();
			// it means that this node has been reached previously
			if (dis[node] != Integer.MAX_VALUE) {
				for (pair an : adj.get(node)) {
					if (dis[node] + an.weight < dis[an.node]) {
						dis[an.node] = dis[node] + an.weight;
					}
				}
			}
		}

		for (int i = 0; i < n; i++) {
			if (dis[i] == Integer.MAX_VALUE)
				System.out.print("INF");
			else
				System.out.print(dis[i] + " ");
		}
		System.out.println();

	}
--------------------------------------------------------------------------------------
7.Dijkstra's ALgorithm  -(Greedy Algo)

//	Shortest Distance from source to every other node in Undirected/Directed Weighted Graph is known as Dijkstra Algorithm
//TC-> O((N+E)logN)
//SC-> O(2N)
	
	public static void DijkstraAlgorithm(int n, int src, ArrayList<ArrayList<pair>> adj) {
		// we will use PriorityQueue here though we can use set also as it works in
		// similar fashion.
		int[] dis = new int[n];
		for (int i = 0; i < n; i++) {
			dis[i] = 1000000000;
		}
		dis[src] = 0;

		// min pq acc to distances
		PriorityQueue<pair> pq = new PriorityQueue<>((a, b) -> (a.weight - b.weight));
		pq.add(new pair(src, 0));

		while (!pq.isEmpty()) {
			pair rp = pq.poll();

            if(dis[rp.node]<rp.weight)continue; //this prevents TLE


			for (pair an : adj.get(rp.node)) {
				if (dis[rp.node] + an.weight < dis[an.node]) {
					dis[an.node] = dis[rp.node] + an.weight;
					pq.add(new pair(an.node, dis[an.node]));
				}
			}
		}
		for (int i = 0; i < n; i++) {
			System.out.print(dis[i] + " ");
		}
		System.out.println();

	}
--------------------------------------------------------------------------------------
8. Minimum Spanning Tree using Prims Algo  -(Greedy Algo)

// When you convert a Undirected Weighted Graph into a tree which has exactly N nodes and (N-1)edges and every node is reachable by every other node. is called 
//	a Spanning tree.There can be multiple Spanning Trees.
//	Among all the spanning trees possible from the graphs , the spanning tree which has minimum cost of edges is called Min Spanning Tree.

Prims->


//	Prims Algorithm-> it is used to find Minimum Spanning tree
//	-> It basically picks up a Node and then it takes the minimal edges connected to it and subsequently it keeps on taking the minimal edges connected
//	to all the nodes. ( take care in account that do not pick the edge which makes cycle.

	// Tc of below implementation is more than N*N.
	public static void PrimsAlgorithm(int n, ArrayList<ArrayList<pair>> adj) {
		int[] key = new int[n];
		boolean[] mstSet = new boolean[n];
		int[] parent = new int[n];

		for (int i = 0; i < n; i++) {
			key[i] = 100000000;
			mstSet[i] = false;
			parent[i] = -1;
		}
		key[0] = 0; // it is done such that mst starts with some node.

		// as Mst has (N-1)edges-->
		for (int i = 0; i < n - 1; i++) {

			// Step-1: Find minimum key value in keyArray which has not been part of MST
			// yet.
			int mini = 100000000;
			int u = 0;
			for (int v = 0; v < n; v++) {
				if (mstSet[v] == false && key[v] < mini) {
					mini = key[v];
					u = v;
				}
			}

			// u is the min key value

			// Step-2: Now make this min key value the part of MST.
			mstSet[u] = true;

			// Step-3: Now traverse through its(u)adjacent nodes and you made sure you
			// updated the key index if weight was lesser and it was not a part of MST.
			for (pair an : adj.get(u)) {
				if (mstSet[an.node] == false && an.weight < key[an.node]) {
					parent[an.node] = u;
					key[an.node] = an.weight;
				}
			}

		}

		// as we started with 0 so it can never have a parent that's why i started with
		// 1.
		for (int i = 1; i < n; i++) {
			System.out.println(parent[i] + " - " + i);
		}

	}
	// To optimize Prims Algo we use PriorityQueue
//	TC-> O((N+E)logN)approx
//	SC-> approx O(N)

	public static void PrimsAlgoOptimised(int n, ArrayList<ArrayList<pair>> adj) {
		int[] key = new int[n];
		boolean[] mstSet = new boolean[n];
		int[] parent = new int[n];

		for (int i = 0; i < n; i++) {
			key[i] = 100000000;
			mstSet[i] = false;
			parent[i] = -1;
		}

		PriorityQueue<pair> pq = new PriorityQueue<>((a, b) -> (a.weight - b.weight));
		key[0] = 0; // it is done such that mst starts with some node.
		pq.add(new pair(0, key[0])); // pair (index-keyValue)

		// as Mst has (N-1)edges-->
		for (int i = 0; i < n - 1; i++) {

			// Step-1: Find minimum key value in PriorityQueue
			int u = pq.poll().node; // this will give me the index at which min key value is present in key array.

			// u is the min key value

			// Step-2: Now make this min key value the part of MST.
			mstSet[u] = true;

			// Step-3: Now traverse through its(u)adjacent nodes and you made sure you
			// updated the key index if weight was lesser and it was not a part of MST.
			for (pair an : adj.get(u)) {
				if (mstSet[an.node] == false && an.weight < key[an.node]) {
					parent[an.node] = u;
					key[an.node] = an.weight;
					pq.add(new pair(an.node, key[an.node]));
				}
			}

		}

		// as we started with 0 so it can never have a parent that's why i started with
		// 1.
		for (int i = 1; i < n; i++) {
			System.out.println(parent[i] + " - " + i);
		}

	}

--------------------------------------------------------------------------------------
9. Minimum Spanning Tree Using Kruskal's ALgo -(Greedy Algo)

->Kruskal uses Disjoint Set

// M->edges, N->Nodes
//T.C-> O(MlogM) for sorting + O(M) for traversing *O(4*alpha)
//S.C-> O(M) + SC for DS
	public static void KruskalAlgo(int n, ArrayList<Node> adj) {
		Collections.sort(adj, (a, b) -> (a.w - b.w));

		int[] parent = new int[n];
		int[] rank = new int[n];

		for (int i = 0; i < n; i++) {
			parent[i] = i;
			rank[i] = 0;
		}

		int cost = 0;
//		Node->(u,v,w)
		ArrayList<Node> mst = new ArrayList<>();

		for (Node it : adj) {
			if (findParent(it.u, parent) != findParent(it.v, parent)) { // different component because if we add the
																		// same component, it will make cycle.
				cost += it.w;
				mst.add(it);
				union(it.u, it.v, parent, rank);
			}
		}
		System.out.println(cost);
		for (Node it : mst) {
			System.out.println(it.u + "-" + it.v);
		}
	}
--------------------------------------------------------------------------------------
#) DISJOINT SET


// Disjoint Set-> Its a kind of data structure used to detect cycle in kruskal algo, the main task of this data structure-> to tell us that a particular node and the 
//		other node belongs to same component or the different component
//		there are two function a) findParent() which finds parent of a node in a component. b) Union(a,b) it joins the two components.
//		The Effective implementation of Disjoint Set is done by { Union by Rank, Path compression } 

//		Path compression-> Suppose if you have component like 4->6->7 which means if we have to find the parent of 7 then we have to go through like 6 is parent of 7
//		then 4 is the parent of 6 .So if the ultimate parent of 7 is 4 then why  don't you point 7 to 4 directly instead of 6. this is called path compression.
//

//		Union By Rank-> Union(a,b) in this we first find the parent of 'a' and parent of 'b' then check their ranks if they are same then increase any one 
//		(prefer smaller no. parent) and then join both component and which parent get selected, make it the parent of whole component, and if ranks are differnt, take the
//		higher rank and do the same task, this is called Union by Rank.
//		Whenever the rank is same then only increase the rank of the selected parent, don't increase when ranks differ because by increasing the rank the height of the tree
//		increases. if we join the larger tree with smaller tree, the depth doesn't increases but if do the exact opposite the depth will increase.

//		Time complexity of both the functions a) find parent b) union  is  O(4*alpha) which is approximately equals to O(4) which is constant TC
//		Space complexity -> O(2N)
	public static void main(String[] args) {

		Scanner scn = new Scanner(System.in);

		makeSet();
		int m = scn.nextInt();
		while (m-- > 0) {
			int u = scn.nextInt();
			int v = scn.nextInt();
			union(u, v);
		}

		int a = scn.nextInt();
		int b = scn.nextInt();
		// if a and b belong to the same component or not.
		if (findPar(a) != findPar(b)) {
			System.out.print("Different Component");
		} else {
			System.out.println("Same Component");
		}

		

	}

	static int[] parent = new int[8];
	static int[] rank = new int[8];

	public static void makeSet() {
		for (int i = 1; i < 8; i++) {
			parent[i] = i; // because we first make the component parent of itself
			rank[i] = 0;
		}
	}

	public static int findPar(int node) {
		if (node == parent[node]) {
			return node;
		}

		return parent[node] = findPar(parent[node]); // by this we are calling as well as compressing path //if we don't
														// do path compression then T.C will be logN
	}

	public static void union(int u, int v) {
		u = findPar(u);
		v = findPar(v);

		if (rank[u] < rank[v]) {
			parent[u] = v;
		} else if (rank[u] > rank[v]) {
			parent[v] = u;
		} else {
			parent[v] = u;
			rank[u]++;
		}

	}


--------------------------------------------------------------------------------------
10. Kosaraju's Algorithm

//	Kosaraju's Algo-> it helps us to find out all the Strongly Connected Components (SCC) in a Directed graph.
//	Strongly connected Components-> it is a component in which if you start with any node you can reach every other node in that component.
//	Intuition-> It tries to have a dfs right starting from the back edges right starting from the back nodes so only those nodes in SCC are visited


	// TC-> O(N+E)
	// SC-> O(N+E)
	public static void KosarajuAlgo(int n, ArrayList<ArrayList<Integer>> adj) {

		// Step-1: Sort all the nodes in order of finishing time.->TopoSort
		Stack<Integer> st = new Stack<>();
		boolean[] vis = new boolean[n];

		for (int i = 0; i < n; i++) {
			if (!vis[i]) {
				DfsTOPO(i, vis, st, adj);
			}
		}

		// Step-2: Tranpose the graph so that you don't end up going to the other part
		// (means apart from SCC). By Transposing means (Reverse all the edges)

		ArrayList<ArrayList<Integer>> transpose = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			transpose.add(new ArrayList<>());
		}

		for (int i = 0; i < n; i++) {
			vis[i] = false;
			for (int it : adj.get(i)) {
				transpose.get(it).add(i);
			}
		}

		// Step-3: Do the Dfs According to the finishing time.
		while (!st.isEmpty()) {
			int node = st.peek();
			st.pop();
			if (!vis[node]) {
				System.out.print("SCC: ");
				revDFS(node, vis, transpose);
				System.out.println();
			}
		}

	}

	public static void revDFS(int node, boolean[] vis, ArrayList<ArrayList<Integer>> transpose) {
		vis[node] = true;
		System.out.print(node+" ");
		for (int it : transpose.get(node)) {
			if (!vis[it]) {
				revDFS(it, vis, transpose);
			}
		}

	}

--------------------------------------------------------------------------------------
11. Bellman Ford ALgorithm


//	This Algorithm is used to find shortest path from source to to every other node, unlike Dijkstra it also works in case of negative weights
//	Dijkstra fails for negative edge weight, eg) suppose you have an edge from u to v having weight = -2 now if you apply dijkstra here it will keep trying
//	to find the shortest path and falls into infinte loop. 

//	Condition in which BellmanFord ALgo doesn't work is the cycle may contained in graph should not be negative. because it negative cycle it will fall int 
//	infinite loop, So using this Algo you can detect the negative cycle.

// BellmanFord Algo works for Directed Graph but if you want it to work for undirected graph just convert into directed graph using bi-directional edges.	
// Algorithm states that after relaxing (n-1) no of times (which basically works for worst case) whatever distance array you have its the shortest.
//	just relax 1 more time if in distance array any distance again reduces then graph contains -ve cycle
//	The intuition behind the (n-1) times relaxation because for n no. of node max path possible is (n-1). so for each time suppose if there is max 1 relaxation.
//	then at the end of n-1 all the nodes get relaxed as src dis is 0;

//	TC-> O(N-1)*O(E)
//	SC-> O(N)

public static void BellmanFordAlgo(int src, int n, ArrayList<Node> edges) {
		int[] dis = new int[n];
		for (int i = 0; i < n; i++) {
			dis[i] = 100000000;
		}
		dis[src] = 0;

//		Node->(u,v,w)
//		Relaxing n-1 number of times.across all the edges
		for (int i = 0; i < n - 1; i++) {
			for (Node node : edges) {
				if (dis[node.u] + node.w < dis[node.v]) {
					dis[node.v] = dis[node.u] + node.w;
				}
			}
		}
// 		Relax one more time to check negative cycle		
		int flag = 0;

		for (Node node : edges) {
			if (dis[node.u] + node.w < dis[node.v]) {
				flag = 1;
				System.out.println("Negative cycle");
				break;
			}
		}
		if (flag == 0) {
			for (int i = 0; i < n; i++) {
				System.out.println(i + " - " + dis[i]);
			}
		}
	}

	public static class Node {
		int u;
		int v;
		int w;

		public Node(int u, int v, int w) {
			this.u = u;
			this.v = v;
			this.w = w;
		}
	}



--------------------------------------------------------------------------------------
#) Applying Dfs on 2D grid.
->Here cell=grid, Common-(sides/sides+corners)=edges,
->Here you can move limited no. of moves max 8 or 4 like top, down, bottom, up, topright etc.

static int[]dx={-1,0,1,0};
static int[]dy={0,1,0,-1};

void dfs(int x,int y){

vis[x][y]=true;

System.out.println(x+" "+y);

for(int i=0;i<4;i++){
    if(isValidCell(x+dx[i],y+dy[i]))
    {
        dfs(x+dx[i],y+dy[i]);
    }
}

// if(isValidCell(x-1,y)) //up
// dfs(x-1,y);

// if(isValidCell(x,y+1))   //right
// dfs(x,y+1);

// if(isValidCell(x+1,y))  //down
// dfs(x+1,y);

// if(isValidCell(x,y-1))      //left
// dfs(x,y-1);

}

boolean isValidCell(int x,int y){
	if(x<0||x>=m||y<0||y>=n){   //0 based indexing on M x N Grid
		return false;
	}
	if(vis[x][y]==true)  //already visited cell
	return false;

	return true;
}
--------------------------------------------------------------------------------------
#) Applying Bfs on 2D grid.


void bfs(int srcX,int srcY){

Queue<Pair>q=new LinkedList<>();
q.add(new Pair(srcX,srcY));
dis[srcX][srcY]=0;
vis[srcX][srcY]=true;
while(!q.isEmpty()){

Pair rp=q.remove();
int currX=rp.x;
int currY=rp.y;
for(int i=0;i<4;i++){
	if(isValidCell(currX+dx[i],currY+dy[i])){
		int newX=currX+dx[i];
		int newY=currY+dy[i];
		q.add(new Pair(newX,newY));
		dis[newX][newY]=dis[currX][currY]+1;
		vis[newX][newY]=true;

	}
}
//print distance array.
}
--------------------------------------------------------------------------------------
12. Minimum Step by knight
 public int minStepToReachTarget(int source[], int target[], int N) {
        boolean visited[][]=new boolean[N+1][N+1];
        int dx[]={-2,-2,-1,-1,1,1,2,2};
        int dy[]={-1,1,-2,2,-2,2,-1,1};
        Queue<Coordinates> q= new LinkedList<>();
        q.add(new Coordinates(source[0],source[1],0));
        while(!q.isEmpty()){
            Coordinates curr=q.remove();
            
            if(curr.x==target[0]&&curr.y==target[1])
                return curr.dist;
            for(int i=0;i<8;i++){
                int x=curr.x+dx[i];
            int y=curr.y+dy[i];
                if(isSafe(x,y,N)&&!visited[x][y]){
                    visited[x][y]=true;
                    q.add(new Coordinates(x,y,curr.dist+1));
                }
            }
        }
        return Integer.MAX_VALUE;
    }
    
    public boolean isSafe(int x,int y,int n){
        return x>=1&&x<=n&&y>=1&&y<=n;
    }
--------------------------------------------------------------------------------------
13. Clone Graph ->https://www.youtube.com/watch?v=f2EfGComRKM

public Node cloneGraph(Node node) {
        
        Node[]vis=new Node[1000];//as we don't know the exact size;
        if(node==null)
            return node;
        
        Node copy=new Node(node.val);
        
        vis[node.val]=copy;
        
        //looping through adjacent nodes of original graph because they contain neighbours;
        for(Node an:node.neighbors){
            if(vis[an.val]==null){
             Node newnode=new Node(an.val);
                copy.neighbors.add(newnode);
                dfs(an,newnode,vis); //we are passing original graph also.(an->adjacent node)
            }else{
                copy.neighbors.add(vis[an.val]);
            }
        }
        
        return copy;
    }
    //an is from original array which contains aj_list of neighbors, whereas
    //nn contain empty list but same value as an.
    public void dfs(Node an,Node nn,Node[]vis){
        vis[nn.val]=nn;
        
        for(Node cn:an.neighbors){
            if(vis[cn.val]==null){
                Node newnode=new Node(cn.val);
                nn.neighbors.add(newnode);
                dfs(cn,newnode,vis);
            }else{
             nn.neighbors.add(vis[cn.val]);   
            }
        }
    }
--------------------------------------------------------------------------------------
14. Number of Operations to make Network Connected.
-> Used Disjoint set.

 public int makeConnected(int n, int[][] connections) {
        if(connections.length<n-1)return -1; //we need atleast n-1 edges to make all connected.
        int[]par=new int[n];
        int[]rank=new int[n];
        
        for(int i=0;i<n;i++){
            par[i]=i;
            rank[i]=0;
        }
        
        int components=n;
        int m=connections.length;
        
        for(int i=0;i<m;i++){
            int p1=findParent(par,connections[i][0]);
            int p2=findParent(par,connections[i][1]);
            if(p1!=p2){
                if(rank[p1]>rank[p2]){
                    par[p2]=p1;
                }else if(rank[p2]>rank[p1]){
                    par[p1]=p2;
                }else{
                    rank[p1]++;
                    par[p2]=p1;
                }    
                components--;
            }
        }
        return components-1; //as we only need the no. of connected components. 
        //and we know that components-1  edges are required to make all connected.
        
    }
    public int findParent(int[]par,int i){
        if(i==par[i])
            return i;
        
        return par[i]=findParent(par,par[i]); //path compression
    }
--------------------------------------------------------------------------------------
15. Number of Islands
*Logic-> Just go through every cell like for(0->row){for(0-col){ c++;  [bfs/dfs] }}; c will give ans. 
--------------------------------------------------------------------------------------
16. Flood Fill ALgo

public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        if (image[sr][sc] == newColor) return image;
        fill(image, sr, sc, image[sr][sc], newColor);
        return image;
    }
    
    private void fill(int[][] image, int sr, int sc, int color, int newColor) {
        if (sr < 0 || sr >= image.length || sc < 0 || sc >= image[0].length || image[sr][sc] != color) return;
        image[sr][sc] = newColor;
        fill(image, sr + 1, sc, color, newColor);
        fill(image, sr - 1, sc, color, newColor);
        fill(image, sr, sc + 1, color, newColor);
        fill(image, sr, sc - 1, color, newColor);
    }
##) Similar problem
-> Replace O's with X's (gfg problem -> https://www.geeksforgeeks.org/given-matrix-o-x-replace-o-x-surrounded-x/ ) 
-> Just apply this algo at each boundry top bottom left right. with newColor as 'X' and old as 'O'.
--------------------------------------------------------------------------------------
17. M-Coloring Problem -O(M^N)
Intuition-> Color every node with each color 
(Backtracking)

//node=0; is passed.
 public static boolean M_ColoringProblem(List<Integer>[]G,int[]color,int node,int m,int n){
        if(node==n)//we have covered all nodes means colored every node acc to condition
            return true;
            
        for(int i=1;i<=m;i++){
            if(isValid(G,color,node,i)){
                color[node]=i;
                if(M_ColoringProblem(G,color,node+1,m,n)){
                    return true;
                }
                color[node]=0;  //backtrack
            }
        }
        return false;
    }
    public static boolean isValid(List<Integer>[]G,int[]color,int node,int col){
        for(int it:G[node]){
            if(color[it]==col)return false;
        }
        return true;
    }
--------------------------------------------------------------------------------------
18. Find Bridges in graph.
-> Below algo is also known as tarjan's Algorithm
->O(N+E), S(2N)

//Bridge in Graph -> Those edges are called bridges in graph on whose removal the graph is broken into 2 or more no. of components.
// Back edges-> A Back edge connects node to its ancestor(atleast grandparent).
// Back edges can never be bridges because there already exists a path(indirect) from ancestor to curr node and backedge is the direct path from curr node to ancestor.
//Back edge create a cycle.
	

	public static void PrintBridges(int n, ArrayList<ArrayList<Integer>> adj) {
		boolean vis[] = new boolean[n];
		int[] tis = new int[n]; // time of insertion means when we enter a node.
		int[] low = new int[n]; // lowest time of insertion. //or the lowest ancestor you can reach through some backedges.

		int timer = 0;
		for (int i = 0; i < n; i++) {
			if (!vis[i]) {
				DFS(i, -1, vis, tis, low, adj, timer);
			}
		}
	}

	private static void DFS(int node, int parent, boolean[] vis, int[] tis, int[] low,
			ArrayList<ArrayList<Integer>> adj, int timer) {
		vis[node] = true;
		tis[node] = low[node] = timer++;

		for (int it : adj.get(node)) {
			if (it == parent)  
				continue;

			if (!vis[it]) {
				DFS(it, node, vis, tis, low, adj, timer);   //forward edge
				if (low[it] > tis[node]) { 
					System.out.println(it + "-" + node); // Bridge in graph
				}

//else -> if low[it]<=tis[node] this means if we remove this edge then there is another edge connected to curr node's parent.(ancestor)-> which is back edge here.
				
				low[node] = Math.min(low[it], low[node]); 

 //after checking for bridge condition curr node also tries to minimize its low time because if child can reach this min value of low[] then curr node can also as it is connected to it by an edge.	

			} else {

				low[node] = Math.min(low[node], tis[it]); 

//so there is a backedge from node-it , so it gets updated because this node is connected to its ancestor here (it). 
		
   			}											 	
		}

	}
--------------------------------------------------------------------------------------
19. Find Articulation point in graph.
->refer above problem to understand more.

// Articulation Point-> It is a node on whose removal the graph is broken down into two or more no. of components.
// An end point of a bridge is an articulation point. if removal of the end point leads to disconnect the graph.
// whatever endpoint have degree more than one is the articulation point.
// Articulation point can exist without the existence of bridges. suppose if a node is connected to 2 or more than two nodes. like a web and the center is 
// articulation point.	
// There is no node whose low time is smaller than insertion time of root.

	
		public static void PrintArticulationPoints(int n, ArrayList<ArrayList<Integer>> adj) {
			boolean vis[] = new boolean[n];
			int[] tis = new int[n]; // time of insertion
			int[] low = new int[n]; // lowest time of insertion.
	
			int[] isArticulation = new int[n];
	
			int timer = 0;
			for (int i = 0; i < n; i++) {
				if (!vis[i]) {
					DFS(i, -1, vis, tis, low, adj, timer, isArticulation);
				}
			}
			for (int i = 0; i < n; i++)
				if (isArticulation[i] == 1)
					System.out.println(i);
		}
	
		private static void DFS(int node, int parent, boolean[] vis, int[] tis, int[] low,
				ArrayList<ArrayList<Integer>> adj, int timer, int[] isArticulation) {
			vis[node] = true;
			tis[node] = low[node] = timer++;
			int child = 0;
	
			for (int it : adj.get(node)) {
				if (it == parent)
					continue;
	
				if (!vis[it]) {
					//forward edge
					DFS(it, node, vis, tis, low, adj, timer, isArticulation);
					low[node] = Math.min(low[it], low[node]);
					if (low[it] >= tis[node] && parent != -1) {
						isArticulation[node] = 1;
					}
					child++;  //to check the subtree connected to root.
				} else {
					//BackEdge
					low[node] = Math.min(low[node], tis[it]);
				}
			}
			if (parent == -1 && child > 1)  // if root of dfs tree has more than 1 subtree than it is an articulation point.
				isArticulation[node] = 1;
	
		}


--------------------------------------------------------------------------------------
20. Journey to moon
Logic-> Firstly make graph from given data, now count size of each component. and now  do this->
->here Pairs store the size of each connected component of the graph.

		ArrayList<Integer> pairs = Bfs(adj, new ArrayList<>(), n);
		int[] suffix = new int[pairs.size()];
		suffix[pairs.size() - 1] = pairs.get(pairs.size() - 1);
		for (int i = suffix.length - 2; i >= 0; i--) {
			suffix[i] += suffix[i + 1] + pairs.get(i);
		}
		long res = 0;
		for (int i = 0; i < suffix.length - 1; i++) {
			res += suffix[i + 1] * pairs.get(i);
		}

		return res;

--------------------------------------------------------------------------------------
21. Minimum time taken by each job to be completed given by a DAG.

-> Use toposort indegree logic and then whenever indegree of adj node become 0 then 
ans[adjnode]=ans[node]+1;
--------------------------------------------------------------------------------------
22. Find whether it is possible to finish all tasks or not from given dependencies/ Course schedule on leetcode
-> in this question toposort with dfs won't work but toposort with bfs works because in bfs we can count the elements which get entered 
in the queue.
->Logic -> we have to find the cycle in directed graph.( so use logic -> dfs on directed graph)

#) Course Schedule 2 (Leetcode 210)
-> Just do toposort and return the linear ordering of the graph. (using BFS)

#) Course Schedule 3 (Leetcode 630)
-> Greedy problem

  public int scheduleCourse(int[][] courses) {
        Arrays.sort(courses,(a,b)->a[1]-b[1]); //Sort the courses by their deadlines (Greedy! We have to deal with courses with early deadlines first)
        PriorityQueue<Integer> pq=new PriorityQueue<>((a,b)->b-a); // to get the longest time taken course.
        int time=0;
        for (int[] c:courses) 
        {
            time+=c[0]; // add current course to a priority queue
            pq.add(c[0]);
            if (time>c[1]) time-=pq.poll(); //If time exceeds, drop the previous course which costs the most time. (That must be the best choice!)
        }        
        return pq.size();
    }

--------------------------------------------------------------------------------------
23. Snake and Ladder -> https://www.youtube.com/watch?v=zWS2fCJGxmU

 public int snakesAndLadders(int[][] board) {
        int n=board.length;
        boolean[][]vis=new boolean[n][n];
        
        int steps=0;
        Queue<Integer>q=new LinkedList<>();
        vis[n-1][0]=true;
        q.add(1);
        
        while(!q.isEmpty()){
            int size=q.size();
            
            for(int i=0;i<size;i++){
                 int x=q.poll();
                if(x==n*n)return steps;
               for(int k=1;k<=6;k++){
                  
                   if(k+x>n*n)break;
                    
                   int[]pos=findCoordinates(k+x,n);
                   int r=pos[0];
                   int c=pos[1];
                   
                   if(!vis[r][c]){
                       vis[r][c]=true;
                       
                       if(board[r][c]==-1){
                            q.add(k+x);    
                       }else{
                           q.add(board[r][c]);
                       }
                   } 
               }          
            }
    
            steps++;              
        }
        return -1;       
    }
    
    public int[] findCoordinates(int curr,int n){  //done this part because the numbers are actually like snake and ladder 
        int r= n - (curr-1)/n - 1;
        int c= (curr-1)%n;
        
        if(r%2==n%2){
            return new int[]{r,n-c-1};
        }
        return new int[]{r,c};
    }

--------------------------------------------------------------------------------------
24. Floyd Warshall ( all pairs shortest path)
-> extended version of dijkstra(single source shortest path)

public void shortest_distance(int[][] matrix)
    {
        somechanges(matrix);//changed -1 to infinity to make code easier.
            int infi=Integer.MAX_VALUE;
            
            int n=matrix.length;
            for(int k=0;k<n;k++){
                for(int i=0;i<n;i++){
                    for(int j=0;j<n;j++){
                        if(matrix[i][k]==infi||matrix[k][j]==infi)continue;
                        matrix[i][j]=Math.min(matrix[i][j],matrix[i][k]+matrix[k][j]);
                        if(matrix[i][j]==infi)
                            matrix[i][j]=-1;
                            
                      }
                  }
           }
    }
--------------------------------------------------------------------------------------
25. Number of Triangles in directed and undirected Graph.

Logic-> we will run three loops for 2 nodes of triangle , each loop will be from (0 to n-1)
Now whenever there will be and edge among them means (arr[i][j]==arr[j][k]==arr[k][i]==1) then count++
it will be mentioned that the given graph is directed or not. 
If Directed graph-> ans=count/3;
If Undirected graph-> ans=count/6; 
--------------------------------------------------------------------------------------
26. Word Ladder
-> logic-> you just have to make a graph, and nodes have adj nodes which have only 1 letter diff, and then apply Bfs but
this making of graph and all will give you TLE.
->So what you can do is you just change every letter of curr word from (a to z) and then check if it exists in vis Map if it is then 
it must be its adjacent having only 1 letter diff.

O(No. of words in wordlist*26*length of each word); 
 public int ladderLength(String src, String tar, List<String> wordlist) {
        
        if(!wordlist.contains(tar))return 0;
    
        HashMap<String,Boolean>vis=new HashMap<>();
        
        for(int i=0;i<wordlist.size();i++){
            vis.put(wordlist.get(i),false);
        }
        
        Queue<String>q=new LinkedList<>();
               
        vis.put(src,true);
        q.offer(src);
        int ans=1;
        
        while(!q.isEmpty()){
            int size=q.size();
            for(int i=0;i<size;i++){
                String w=q.poll();
                
                if(w.equals(tar))return ans;
                
                wordMatch(w,vis,q);             
            }
            ans++;         
        }
        return 0;
    }
    public void wordMatch(String word,HashMap<String,Boolean>vis,Queue<String>q){
        
        char[] arr=word.toCharArray();
        for(int i=0;i<arr.length;i++){
            char ch=arr[i];
            for(int j=0;j<=26;j++){
                
                char temp=(char)('a'+j);
                arr[i]=temp;
                
                String str=new String(arr);
                if(vis.containsKey(str) && vis.get(str)==false){
                    vis.put(str,true);
                    q.offer(str);
                }
            }
            arr[i]=ch;
        }        
    }
--------------------------------------------------------------------------------------
27. Total no. of spanning Trees in a Graph
->use Kirchhoff's Matrixo-Tree Theorem

--------------------------------------------------------------------------------------
28. Longest Path in a Directed Acyclic Graph

-> Solution is same as finding shortest distance from source to every other node in DAG.
we use toposort.

public static void LongestPathDirectedAcyclicGraph(int n, int src, ArrayList<ArrayList<pair>> adj) {
		Stack<Integer> st = new Stack<>();
		boolean[] vis = new boolean[n];

		for (int i = 0; i < n; i++) {
			if (!vis[i]) {
				TopoSortDfs(i, vis, st, adj);
			}
		}
		int[] dis = new int[n];
		for (int i = 0; i < n; i++) {
			dis[i] = Integer.MIN_VALUE;
		}
		dis[src] = 0;

		while (!st.isEmpty()) {
			int node = st.pop();
			// it means that this node has been reached previously
			if (dis[node] != Integer.MIN_VALUE) {
				for (pair an : adj.get(node)) {
					if (dis[node] + an.weight > dis[an.node]) {
						dis[an.node] = dis[node] + an.weight;
					}
				}
			}
		}

		for (int i = 0; i < n; i++) {
			if (dis[i] == Integer.MIN_VALUE)
				System.out.print("INF");
			else
				System.out.print(dis[i] + " ");
		}
		System.out.println();

	}


--------------------------------------------------------------------------------------
29. Longest Increasing Path in a matrix (leetcode 329 )

 public int longestIncreasingPath(int[][] matrix) {
        
		//Base condition
        if(matrix.length==0)
            return 0;
        
		
        int dp[][] = new int[matrix.length][matrix[0].length];
        int max = 0;
        
        for(int i =0;i<matrix.length;i++){
            for(int j =0;j<matrix[0].length;j++){
                //result is not stored
                if(dp[i][j]==0){
                   dfs(matrix,i,j,Integer.MIN_VALUE,dp);
                   max = Math.max(dp[i][j],max); 
                }
            }
        } 
        return max;
    }
    
    private int dfs(int[][] matrix,int i,int j,int pre,int[][] dp){
        //Dont go beyond boundaries and next element should be greater for increasing path
        if(i<0 || j<0 ||i>=matrix.length || j>=matrix[0].length || pre>=matrix[i][j])
            return 0;
			
		//already explored
        else if(dp[i][j]!=0) return dp[i][j];
        
		//exploring all direction
        int pathOne = dfs(matrix,i+1,j,matrix[i][j],dp);
        int pathTwo = dfs(matrix,i-1,j,matrix[i][j],dp);
        int pathThree = dfs(matrix,i,j-1,matrix[i][j],dp);
        int pathFour = dfs(matrix,i,j+1,matrix[i][j],dp);
        
		//finding the max path
        int maxOne = Math.max(pathOne,pathTwo);
        int maxTwo = Math.max(pathThree,pathFour);
        
		//store maximum path on that index
        dp[i][j] = 1+Math.max(maxOne,maxTwo);
        
        return dp[i][j];   
    }
--------------------------------------------------------------------------------------
30. Water Jug Problem (Kind of puzzle)
->https://www.youtube.com/watch?v=0Oef3MHYEC0

public boolean canMeasureWater(int x, int y, int z) {
    //limit brought by the statement that water is finallly in one or both buckets
    if(x + y < z) return false;
    //case x or y is zero
    if( x == z || y == z || x + y == z ) return true;
    
    //get GCD, then we can use the property of Bézout's identity
    return z%GCD(x, y) == 0;
}

public int GCD(int a, int b){
    while(b != 0 ){
        int temp = b;
        b = a%b;
        a = temp;
    }
    return a;
}
--------------------------------------------------------------------------------------
31. Minimum Edges to Reverse to make Path from a source to a Destination

Logic-> just mark 0 weight on given edge and add another oppo edge with weight 1, do this for every edge on the graph.
And then Apply Dijkstra Algo to find the shortest path from source to destination.

--------------------------------------------------------------------------------------
32. Find if there is a path of more than k length from a source
->
Longest Path is a NP Hard
if we are able to solve this problem in Polynomial we can solve the Longest Path also in Polynomial
so Exponential is the best we can do

O(N!)
boolean pathMoreThanKUtil(int src, int k, boolean[] path)
    { 
       
      // If k is 0 or negative, return true;
      if (k <= 0)
        return true;
 
      ArrayList<AdjListNode> it = adj.get(src);
 
      for(int i = 0; i < adj.get(src).size(); i++)
      {
        AdjListNode vertex = adj.get(src).get(i);
 
        int v = vertex.v;
        int w = vertex.weight;

        if (path[v] == true) //means there is cycle from this path.
          continue;

        if (w >= k)
          return true;

        path[v] = true;
 
        if (pathMoreThanKUtil(v, k-w, path))
          return true;
 
        path[v] = false;  //backtracking
      }
      
      return false;
    }

--------------------------------------------------------------------------------------
33. Two Cliques
-> In this question just change the adjacency list as follows
0->{1,2,3}     0->{4}     
1->{0,2}       1->{3,4}
2->{1,0}       2->{3,4} 
3->{0,4}       3->{1,2}
4->{3}         4->{0,1,2} 

Make Graph of new adjacency list and check whether it is Bipartite of not. if it is Bipartite
then it can be divided into two cliques.

Intuition-> in bipartite graph nodes get separated into two sets (color-A and color-B) 
the nodes in these sets are not connected to each other. so if we made graph of reverse of adj list then we should think its reverse that nodes in both the sets are connected to each other as in individual set. 
--------------------------------------------------------------------------------------
34. Alien Dictionary
-> we basically check every adjacent word from dictList and find where there is mismatch of letter 
whenever there is mismatch we just make an directed edge from (misMatched letter from currString to mismatch letter to nextString) and afterthat we just apply Toposort using Kahn's algo.

public static String AlienOrder(String[] words) {
    
		HashMap<Character, HashSet<Character>> graph = new HashMap<>();
		HashMap<Character, Integer> indegree = new HashMap<>();

		for (String str : words) {
			char[] crr = str.toCharArray();
			for (char ch : crr) {
				indegree.put(ch, 0);
			}
		}

		for (int i = 0; i < words.length - 1; i++) {
			String curr = words[i];
			String next = words[i + 1];

			int len = Math.min(curr.length(), next.length());

			boolean flag = false;
			for (int l = 0; l < len; l++) {
				char ch1 = curr.charAt(l);
				char ch2 = next.charAt(l);

				if (ch1 != ch2) {
					HashSet<Character> set = new HashSet<>();
					if (graph.containsKey(ch1)) {
						HashSet<Character> set = graph.get(ch1);

						if (!set.contains(ch2)) {
							set.add(ch2);
							indegree.put(ch2, indegree.get(ch2) + 1);
							graph.put(ch1, set);
						}
					} else {
						set.add(ch2);
						indegree.put(ch2, indegree.get(ch2) + 1);
						graph.put(ch1, set);
					}

					flag = true;
					break;
				}
			}

			if (!flag && curr.length() > next.length()) {  //edge case given in question that if not mismatch then give min length first but 
				return "";                             // here curr have already larger length than next.   
			}
		}
		// now applying Kahn's algo (toposort)

		Queue<Character> q = new LinkedList<>();

		for (char ch : indegree.keySet()) {
			if (indegree.get(ch) == 0) {
				q.offer(ch);
			}
		}

		int count = 0; // taken this to check if there is cycle or not.
		StringBuilder ans = new StringBuilder();

		while (!q.isEmpty()) {
			char rc = q.poll();
			ans.append(rc);
			count++;

			if (graph.containsKey(rc)) {
				HashSet<Character> nbrs = graph.get(rc);
				for (char nbr : nbrs) {
					indegree.put(nbr, indegree.get(nbr) - 1);
					if (indegree.get(nbr) == 0) {
						q.offer(nbr);
					}
				}
			}
		}

		if (count == indegree.size()) {
			return ans.toString();
		}

		return "";
  }

--------------------------------------------------------------------------------------
35. Cheapest Flights Within K Stops
->Simply used Dijkstra algo

//dry run the code to understand 

class Pair {
	int city, cost;

	Pair(int city, int cost) {
		this.city = city;
		this.cost = cost;
	}
}

class City {
	int city, distFromSrc, costFromSrc;

	City(int city, int distFromSrc, int cost) {
		this.city = city;
		this.distFromSrc = distFromSrc;
		this.costFromSrc = cost;
	}
}
class Solution {

public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
	// DFS
    if(n <= 0 || flights == null || flights.length == 0 || K < 0)
    	return -1;

    List<List<Pair>> graph = new ArrayList<>();
    this.buildGraph(graph, n, flights);

    Queue<City> pQueue = new PriorityQueue<>((City c1, City c2) -> c1.costFromSrc - c2.costFromSrc);
    pQueue.offer(new City(src, 0, 0));
    
    HashMap<Integer, Integer> seen = new HashMap<>(); //mandatory to reduce time complexity

    while (!pQueue.isEmpty()) {
    	City top = pQueue.poll();

	if (top.city == dst) {
    		return top.costFromSrc;  
    	}

//Just checking whether the we visited it before and the number of stops that we covered before was low than the current route, then following the current route is not a good idea, so we skip it
        if(seen.containsKey(top.city) && seen.get(top.city)<=top.distFromSrc) 
		continue; 					
            
        seen.put(top.city, top.distFromSrc);
        

    	if (top.distFromSrc > K) {  //because here we can say that we exceeded value ok k, since at above condition we have max value of stops == k which is not giving the destination

    		continue;
    	}

    	List<Pair> neighbors = graph.get(top.city);
    	for (Pair neighbor: neighbors) {
    		pQueue.offer(new City(neighbor.city, top.distFromSrc + 1, top.costFromSrc + neighbor.cost));
    	}
    }

    return -1;
}

private void buildGraph(List<List<Pair>> graph, int n, int[][] flights) {
	for (int i = 0; i < n; i++) {
		graph.add(new ArrayList<>());
	}

	for (int[] flight: flights) {
		graph.get(flight[0]).add(new Pair(flight[1], flight[2]));
	}
}
}
--------------------------------------------------------------------------------------
# Euler Tour Concept-> It helps us to find whether a node is in subtree of other node.
For this while traversing through DFS Algorithm just find the inTime and outTime of each node.
now if we want to check whether x is in subtree of y then we have to check that.

(in[x]>in[y] && out[x]<out[y]) if this gives true then x is in subtree of y.

public static void DFS(boolean[]vis,int node,int[]in,int[]out,ArrayList<ArrayList<Integer>>graph){
        vis[node]=true;
        in[node]=timer++;
        for(int an:graph.get(node)){
            if(!vis[an]){
                DFS(vis,an,in,out,graph);
            }
        }
        out[node]=timer++;
    }
--------------------------------------------------------------------------------------
36. Oliver and the Game

static int timer = 1;

	public static void OliverAndGame(int n, ArrayList<ArrayList<Integer>> graph) {
		int[] in = new int[n+1];
		int[] out = new int[n+1];

		boolean[] vis = new boolean[n+1];
		
		DFS(vis, 1, in, out, graph);

		// run for q queries

		int q = scn.nextInt();
		while (q-- > 0) {
			int type = scn.nextInt();
			int x = scn.nextInt();
			int y = scn.nextInt();
			if (!checkForSubtree(x, y, in, out) && !checkForSubtree(y, x, in, out)) {
				System.out.println("NO");
				continue;
			}

			if (type == 0 && checkForSubtree(x, y, in, out)) {
				System.out.println("YES");
			} else if (type == 1 && checkForSubtree(y, x, in, out)) {
				System.out.println("YES");
			} else {
				System.out.println("NO");
			}
		}
	}
--------------------------------------------------------------------------------------
37. All the ancestors of a Node in a Directed Acyclic Graph
-> Intuition : Reverse all the edges of the graph, so that a node can reach to all of its ancestor.
-> Now, just apply Dfs for each node. separately (new-visited array every time)

 public static List<List<Integer>> getAncestors(int n, int[][] edges) {
       
       //reverse all the edges of the graph.
       // in this way you can reach to all the ancestors of a node.
		List<List<Integer>> adj = makeReverseGraph(n, edges);

		List<List<Integer>>ans = new ArrayList<>();
       
        for(int i=0;i<n;i++){
                int[]vis=new int[n];
                List<Integer>temp = new ArrayList<>();
                Dfs(i,i,adj,temp,vis);
                Collections.sort(temp);
                ans.add(temp);
        }
		return ans;
	}
    public static void Dfs(int node,int source,List<List<Integer>>adj,List<Integer>list,int[]vis){
       vis[node]=1; 
        
        if(node!=source)list.add(node);
        
        for(int an:adj.get(node)){
            if(vis[an]==0){
                Dfs(an,source,adj,list,vis);
            }
        }
    }

--------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------
# Ford-Fulkerson Algorithm for Maximum Flow Problem