Skip to content

Instantly share code, notes, and snippets.

View ssshukla26's full-sized avatar
💭
Learn Apply Repeat

Sunny Shukla ssshukla26

💭
Learn Apply Repeat
View GitHub Profile
@ssshukla26
ssshukla26 / MinCostMST.py
Created August 22, 2021 23:53
Krushkal's With Union-Find (path compression)
"""
References:
https://www.youtube.com/watch?v=JZBQLXgSGfs
https://www.youtube.com/watch?v=kaBX2s3pYO4
"""
class Solution:
# The purpose of find with path compression is to reduce the
# no. of hopes needed to determine the parent node. This reduction
# will help to decrease overall runtime from O(n) to O(log n)
@ssshukla26
ssshukla26 / FindBridges.py
Created August 22, 2021 23:18
Find Bridges Using Targan's Algorithm
# Targan Alog: https://www.youtube.com/watch?v=ZeDNSeilf-Y
# Find Bridges: https://www.youtube.com/watch?v=Rhxs4k6DyMM&t=0s
# Reference: https://gist.github.com/SuryaPratapK/2774cb957a27448b485609418e272f2b
# Find Bridges using Targan Algo
from typing import List, Set, Dict
class Solution():
def __init__(self) -> None:
self.timer = 0
@ssshukla26
ssshukla26 / Tarjan.py
Created August 21, 2021 19:06
Tarjan Algorithm In Python
# Reference : https://www.youtube.com/watch?v=ZeDNSeilf-Y
from typing import List
class Solution():
def __init__(self) -> None:
self.timer = 0
self.discovery = []
self.low = []
@ssshukla26
ssshukla26 / Kosaraju.py
Created August 21, 2021 19:05
Kosaraju Algorithm In Python
# Find Strongly Connected Components in a Graph using Kosaraju Algo
# Reference : https://www.youtube.com/watch?v=Rs6DXyWpWrI
from typing import List, Set
class Solution():
def reverseEdges(self, edges: List[List[int]]) -> List:
edges_rev = [list() for _ in range(len(edges))]