Graphs

Question 1

Clone graph

Question 2

Course schedule (with Course Schedule II Follow Up)

Answer 2

POST ORDER DFS

1) Maintain a adj list :
called premap which will include all course as keys and it’s pre reqs as values, preMap = {i : [] for i in numCourses), we use i since course number are from 0 to numCourses-1

2) Write DFS :
a set called visited for loop detection,
in dfs we call for crs,
it it has no pre req, we can take is so return true.
If it’s in visited, we are in a loop, so return false
otherwise we put it in visited, run dfs on each of it’s pre req, if even one of pre dfs returns false, it means we cant take the crs itself, so return False
otherwise we can take it, so remove from visited as we done visiting the course,set it’s pre req as empty and return True

3.Call DFS :
for each course in numCourses, we call dfs, if we cant take even 1 course, return False
otherwise return True means we can take all courses.

follow up : course schedule II :
we also maintain a cycle set, and in dfs : if in cycle, means loop, so return False
if in visited, means no cycle, so return True
otherwise, add to cycle, run dfs on all pre, and remove from cycle, add to visited, add to result list.
finally call on each crs and return res, if any one crs return False, return empty list

Question 3

Pacific Atlantic waterflow

Question 4

Number of islands

Question 5

Longest consecutive sequence

Question 6

Alien Dictionary

Answer 6

POST ORDER DFS

Create adj list:
This adjacency list will contain each letters in the words and letters that follow those letters,
So adj {char : [all chars that comes after this char]}, also we use set to avoid duplicates

1) adj ={char : set() for each char in words}
2) for each pair, for words in pair, see if order not valid, if valid, find first different char, put word2 char in word 1 char list and break

Write dfs :
visited = {}, res = []
pass a char in dfs, if visited, return that value from visited
Else, set visited to true for that char, for each of it’s neighbors in adj list, run dfs, if any is true, means a loop so return true
Set visited to False now(out of path) and put the char in res (dfs post order)

Call dfs :
For each char, call dfs, if any return True, means loop exists, so return “”, else reverse res (cuz we did post order) and convert to string and return

Question 7

Graph Valid Tree (Cycle Detection in Undirected Graph)

Answer 7

1) Create Adj list, for each node, we will have list of it’s neighbors
since our edges are given in pairs, each in pair is essentially a node connected to each other, so for each pair in edges, we put them to each others adj list

2) Write DFS :
Visited set() to avoid adding same node in visited list twice, dfs takes a node and it’s parent.
if node in visited, loop exists, we return False
otherwise we add it to visited, we run dfs on each of it’s neighbors
for each neighbor,
if it’s same as the nodes’s parent pre, we dont need to visit, so we continue
otherwise we run dfs on neighbors and our old node becomes the parent,
if any of neighbors dfs is false, means loop detected, we return False
otherwise no loop detected, so return True

3.Call DFS : start at 0 and -1, since 0 has no parent, if it returns true (means no loop) and len(visited) == n, means we are able to traverse all nodes from 0, means its connected, we return True, So it’s a valid Tree

Question 8

Number Of Connected Components