# Untitled

unknown
plain_text
22 days ago
15 kB
3
Indexable
Never
```from collections import deque, defaultdict
import heapq

class GraphAlgorithms:
def __init__(self, n):
self.n = n
self.adj = defaultdict(list)

def add_edge(self, u, v, weight=1, directed=False):
self.adj[u].append((v, weight))
if not directed:
self.adj[v].append((u, weight))

def bfs(self, start):
visited = [False] * self.n
queue = deque([start])
visited[start] = True
bfs_order = []

while queue:
node = queue.popleft()
bfs_order.append(node)
for neighbor, _ in self.adj[node]:
if not visited[neighbor]:
queue.append(neighbor)
visited[neighbor] = True
return bfs_order

def dfs(self, start):
visited = [False] * self.n
dfs_order = []

def _dfs(node):
visited[node] = True
dfs_order.append(node)
for neighbor, _ in self.adj[node]:
if not visited[neighbor]:
_dfs(neighbor)

_dfs(start)
return dfs_order

def dijkstra(self, start):
distances = {i: float('inf') for i in range(self.n)}
distances[start] = 0
priority_queue = [(0, start)]

while priority_queue:
current_distance, current_node = heapq.heappop(priority_queue)
if current_distance > distances[current_node]:
continue
for neighbor, weight in self.adj[current_node]:
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))

return distances

def bellman_ford(self, start):
distances = [float('inf')] * self.n
distances[start] = 0
for _ in range(self.n - 1):
for u in self.adj:
for v, weight in self.adj[u]:
if distances[u] != float('inf') and distances[u] + weight < distances[v]:
distances[v] = distances[u] + weight
# Check for negative-weight cycles
for u in self.adj:
for v, weight in self.adj[u]:
if distances[u] != float('inf') and distances[u] + weight < distances[v]:
return "Graph contains a negative-weight cycle"
return distances

def floyd_warshall(self):
dist = [[float('inf')] * self.n for _ in range(self.n)]
for i in range(self.n):
dist[i][i] = 0
for u in self.adj:
for v, weight in self.adj[u]:
dist[u][v] = weight
for k in range(self.n):
for i in range(self.n):
for j in range(self.n):
if dist[i][j] > dist[i][k] + dist[k][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist

def kruskal(self, edges):
def find(parent, i):
if parent[i] == i:
return i
return find(parent, parent[i])

def union(parent, rank, x, y):
root_x = find(parent, x)
root_y = find(parent, y)
if rank[root_x] < rank[root_y]:
parent[root_x] = root_y
elif rank[root_x] > rank[root_y]:
parent[root_y] = root_x
else:
parent[root_y] = root_x
rank[root_x] += 1

edges.sort(key=lambda x: x[2])
parent = [i for i in range(self.n)]
rank = [0] * self.n
mst = []
mst_weight = 0

for u, v, weight in edges:
root_u = find(parent, u)
root_v = find(parent, v)
if root_u != root_v:
mst.append((u, v, weight))
mst_weight += weight
union(parent, rank, root_u, root_v)

return mst, mst_weight

def prim(self):
visited = [False] * self.n
min_heap = [(0, 0)]  # (weight, vertex)
mst_weight = 0
mst_edges = []

while min_heap:
weight, u = heapq.heappop(min_heap)
if visited[u]:
continue
visited[u] = True
mst_weight += weight
for v, w in self.adj[u]:
if not visited[v]:
heapq.heappush(min_heap, (w, v))
mst_edges.append((u, v, w))

if all(visited):
return mst_edges, mst_weight
else:
return None  # MST does not exist

def kosaraju(self):
def dfs(v, visited, stack):
visited[v] = True
for u, _ in self.adj[v]:
if not visited[u]:
dfs(u, visited, stack)
stack.append(v)

def dfs_rev(v, visited, component):
visited[v] = True
component.append(v)
for u, _ in reversed_adj[v]:
if not visited[u]:
dfs_rev(u, visited, component)

stack = []
visited = [False] * self.n
for i in range(self.n):
if not visited[i]:
dfs(i, visited, stack)

reversed_adj = defaultdict(list)
for u in self.adj:
for v, _ in self.adj[u]:
reversed_adj[v].append((u, 1))

visited = [False] * self.n
scc = []
while stack:
v = stack.pop()
if not visited[v]:
component = []
dfs_rev(v, visited, component)
scc.append(component)

return scc

def traveling_salesman(self, graph):
dp = [[None] * (1 << self.n) for _ in range(self.n)]

def tsp(pos, mask):
if mask == (1 << self.n) - 1:
return graph[pos][0]
if dp[pos][mask] is not None:
return dp[pos][mask]

ans = float('inf')
for city in range(self.n):
if mask & (1 << city) == 0:
ans = min(ans, graph[pos][city] +
tsp(city, mask | (1 << city)))
dp[pos][mask] = ans
return ans

return tsp(0, 1)

def largestBst(self, root):
#code here
max_size=0
def check_Bst(root,larger,smaller):
nonlocal max_size
if root is None:
return True,0
larger=max(root.data,larger)
smaller=min(smaller,root.data)
left,a=check_Bst(root.left,larger,root.data)
right,b=check_Bst(root.right,root.data,smaller)
max_size=max(max_size,max(a,b))
if left and right:
if root.data>larger and root.data<smaller:
if root.left and root.right:
if root.data>root.left.data and root.data<root.right.data:
return True,1+a+b
else:
return False,0
if root.left and root.right is None:
if root.data>root.left.data :
return True,1+a
else:
return False,0
if root.right and root.left is None:
if root.data<root.right.data :
return True,1+b
else:
return False,0
elif root.left is None and root.right is None:
return True,1
else:
return False,0
else:
return False,0

_,a=check_Bst(root,float('-inf'),float('inf'))
return max(max_size,a)

class TrieNode:
def __init__(self):
self.childNode = [None] * 26
self.wordEnd = False

class Trie:
def __init__(self):
self.root = TrieNode()

def insert(self, string):
curr_node = self.root
for c in string:
if curr_node.childNode[ord(c)-ord('a')] is None:
node = TrieNode()
curr_node.childNode[ord(c)-ord('a')] = node

curr_node = curr_node.childNode[ord(c)-ord('a')]
curr_node.wordEnd = True

def search(self, key):
curr_node = self.root
for c in key:
if curr_node.childNode[ord(c)-ord('a')] is None:
return False
curr_node = curr_node.childNode[ord(c)-ord('a')]
return curr_node.wordEnd

def delete(self, key):
def dele(root, key, index):
if index == len(key) and root.wordEnd:
return None
if root.childNode[ord(key[index])-ord('a')]:
root.childnode[ord(
key[index])-ord('a')] = dele(root.childNode[ord(key[index])-ord('a')], key, index+1)
if root.wordEnd == False:
return None
return root
self.root = dele(self.root, key, 0)

def wordBreak(self, key):
def check(root, key, i):
if i == len(key):
return root.wordEnd
if root.childNode[ord(key[i])-ord('a')] is None:
return False
if root.childNode[ord(key[i])-ord('a')].wordEnd:
if check(self.root, key, i+1):
return True
return check(root.childNode[ord(key[i])-ord('a')], key, i+1)
return 1 if check(self.root, key, 0) else 0

def wordBreak_dp(self, key):
dp = [False]*(len(key)+1)
dp[0] = 1

for i in range(1, len(key)+1):
for j in range(i-1, -1, -1):
if dp[j] and self.search(key[j:i]):
dp[i] = True
break

return dp[len(key)]

class DynamicProgramming:
def __init__(self) -> None:
pass

def Longest_increasing_subarray(self, nums):
# basic approach we maintain a dp to write the max length of increasing subarray till index i as 1 initially
#  then we go backwards from each index that is from 0 to 0 1 to 0 n-1 to 0
# since we are going backwards we need to check if a num is smaller than the one we are going back from and update the dp value if the value is smaller than
dp = [1]*len(nums)
for i in range(0, len(nums)):
for j in range(0, i):
if nums[i] > nums[j] and dp[j]+1 > dp[i]:
dp[i] = dp[j]+1
# same can be used for any kind of longest subsequence with just changing the condition
return max(dp)

def catalan(self, n):
# Base Case
if n <= 1:
return 1

# Catalan(n) is the sum
# of catalan(i)*catalan(n-i-1)
res = 0
for i in range(n):
res += self.catalan(i) * self.catalan(n-i-1)

return res

def longest_common_subsequence(self, text1, text2):
dp = [[0 for _ in range(len(text1)+1)] for _ in range(len(text2)+1)]

for i in range(1, len(text2)+1):
for j in range(1, len(text1)+1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1]+1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])

return dp[len(text2)][len(text1)]

def editDistance(self,text1,text2):
dp = [[0 for _ in range(len(text1)+1)] for _ in range(len(text2)+1)]
dp[0][0]=0
for i in range(1, len(text2)+1):
dp[i][0]=i

for j in range(1, len(text1)+1):
dp[0][j]=j

for i in range(1, len(text2)+1):
for j in range(1, len(text1)+1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(dp[i-1][j-1],min(dp[i-1][j], dp[i][j-1]))+1

return dp[len(text2)][len(text1)]

def equal_sum_partition(self,arr):
total_sum=0
for num in arr:
total_sum+=num
if total_sum%2==1:
return False
dp=[False for _ in range((total_sum//2)+1)]
dp[0]=True
for i in range(len(arr)):
for S in range(total_sum//2,arr[i]-1,-1):
if dp[S-arr[i]]:
dp[S]=True

return dp[total_sum//2]

def circular_houseRobbery(self,arr):
dp=[num for num in arr]
n=len(arr)
if len(arr)>1:
# start from 0
dp[1]=max(dp[1],dp[0])
for i in range(2,n-1):
dp[i]=max(dp[i-1],dp[i-2]+dp[i])

m1=max(dp)
dp=[num for num in arr]

# starting from 1
dp[2]=max(dp[1],dp[2])
for i in range(3,n):
dp[i]=max(dp[i-1],dp[i-2]+dp[i])
m2=max(dp)
return max(m1,m2)
return max(dp)

def longestPalinSubseq(self, S):
# just longest common substring in string and reverse
dp=[[-1 for _ in range(len(S)+1)] for _ in range(len(S)+1)]

for i in range(len(S)+1):
dp[i][0]=0
dp[0][i]=0

rev=""
for l in S:
rev+=l
rev=rev[::-1]

for i in range(1,len(S)+1):
for j in range(1,len(S)+1):
if S[i-1]==rev[j-1]:
dp[i][j]=dp[i-1][j-1]+1
else:
dp[i][j]=max(dp[i-1][j],dp[i][j-1])

return dp[len(S)][len(S)]

def longest_repeating_subsequence(self,S):
return self.longest_common_subsequence(S,S)

class Greedy():
def ActivitySelection(self,start,end):
pairs=[]
for i in range(len(start)):
pairs.append([start[i],end[i]])

pairs.sort(key=lambda x:x[1])

end_time=pairs[0][1]
activity=1
for i in range(1,len(pairs)):
if pairs[i][0]>end_time:
activity+=1
end_time=pairs[i][1]
return activity

def minPartition(self, N):
# code here
coins=[1,2,5,10,20,50,100,200,500,2000]

i=len(coins)-1
ans=[]

while N!=0:
if N>=coins[i]:
N-=coins[i]
ans.append(coins[i])
else:
i-=1

return ans

def minSum(self, arr, n):
if n==1:
return arr[0]
arr=sorted(arr)
num1=''
num2=''
for i in range(n):
if i%2==0:
num1+=(str(arr[i]))
else:
num2+=(str(arr[i]))

return int(num1)+int(num2)

def fractionalknapsack(self, w,arr,n):
for i in range(n):
arr[i].value=float(arr[i].value/arr[i].weight)

arr.sort(key=lambda x:x.value)
arr.reverse()
ans=0
i=0
while w and i<len(arr):
if arr[i].weight<=w:
ans+=arr[i].value*arr[i].weight
w-=arr[i].weight
else:
ans+=arr[i].value*w
w-=w
i+=1

return ans
# code here

# vszjvnlnvc ```
Leave a Comment