37. Graphs-3 (cycle undir)

# Cycle detection in undirected graphs-

- if during traversal, we find a visited non-parent node as a neighbour of a node,
then cycle is present
- in dfs, take: int par, as another argument
- in bfs, modify queue to store parent for each node
------------------------
1. using BFS    

------------------------------------------------
2. using DFS   

-------------------------------------------------------------------------------------------------------------
1. Bipartite graph check

Ques- colour a graph with 2 colours such that no 2 adjacent nodes have same colour
Info- a graph is bipartite if it is linear or it has even length cycle
-------------------------
Algo- if you encounter a visited non parent node which has same colour as the current node, then graph is not bipartite
-----------------------------
1. using BFS: 
- instead of visited array we will take colour array
- also here we do not need parent node info, as colour array has enough info
--------------------------------------------------------
2. using DFS
---------------------------------------------------------------------------------------------------------------

Comments

Post a Comment

Popular posts from this blog

30.) DP on subsequences

Image
Subset sum = target✅⭐ Partition equal subset sum✅ Partition array into 2 subsets with min abs [sum(v1)-sum(v2) ]✅ Count subsets with sum k✅⭐ Count partitions with given diff✅ target sum✅ 0/1 knapsack✅⭐ min coins✅---->count min coins to be taken coin change-2--->count n(ways) of taking coins⭐✅ unbounded knapsack✅ rod cutting problem✅ ----------------------------------------------------------------------------------------------------------------------------- 2 ways to generate all subsequences- Power Set, or Recursion subset means subsequence in dsa ----------------------------------------------------------------------------------------------------------------------------- 1. Target Sum- QUES- return true if there exists a subset with sum equal to the target in the array... Soln assuming all array elements are positive  here f(n-1,target) will tell if there's a subsequence till n-1 index with sum = target 1.) RECURSIVE SOLN-        ( time: 2^n    ...
Read more

36. Graphs-2 (traversal problems)

Image
1. No. of provinces Count total components in a graph, using any traversal technique ----------------------------------------------------------------------------------------------------------------------------- 2. Rotten oranges⭐     Multi source BFS time: O(n*m)   space: O(n*m) -------------- - count all fresh at start and then count if these many will rot in the process or not - here we do not need a visited matrix since we can modify given - we update time each time there rots atleast one orange in a BFS cycle --------------------------------------------------------------------------------------------------------------------------- 3. No. of Islands Count no. of islands (land surrounded by water in 4 directions) ---------------------------------------------------- time: O(n^2)  space: O(n^2) No. of islands = no. of graph components ----------------------------------------------------------------------------------------------------------------------------- 4. ...
Read more

35. Graphs-1 (basics)

Image
# Note -  1. it has nodes/vertices (N) connected by edges (E) 2. d egree(N)  = n(edges) connected to a node 3. in-degree(N) = no. of in-going edges  4. out-degree(N) = no. of out-going edges  5.  Total degree of undirected graph = (2*E) 6.  DAG - directed acyclic graph 7.  Path -  a sequence of nodes where all  adj nodes have a direct edge b/w them -------------------------------------------------------------------------------------------------------------------------- 1. Representation- 1. Adjacency Matrix:  space: O(n^2) store info about presence of edges between 2 nodes -------------------------------------------------------- 2. Adjacency list:   space: O(n) - store info about adjacent neighbours of a node - for unweighted graph instead of a pair we will store them as integer array ----------------------------------------------------------------------------------------------------------------------------- 2. BFS- time: O(N+...
Read more