[Python] Graph Algorithms One Place for quick revision

from collections import defaultdict
import heapq
class Solution:
    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
        graph = defaultdict(list)
        for i,j,w in times:
            graph[i].append((j,w))
        heap = [(0,K)]
        array = [0] + [float("inf")] * N
        while heap:
            time,ele = heapq.heappop(heap)
            if time < array[ele]:
                array[ele] = time
                for j,w in graph[ele]:
                    heapq.heappush(heap,(time+w,j))
        if max(array) < float("inf"):
            return max(array)
        else:
            return -1
        

class Solution:
    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
        array = [0] + [float("inf")] * N
        array[K] = 0
        for node in range(1,N):
            for u,v,w in times:
                if array[u] + w < array[v]:
                    array[v] = array[u] + w
        if max(array) < float("inf"):
            return max(array)
        else:
            return -1

class Solution:
    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
        dist = [[float("inf") for i in range(N)] for j in range(N)]
        for i in range(N):
            dist[i][i] = 0
        for u,v,w in times:
            dist[u-1][v-1] = w
        for k in range(N):
            for i in range(N):
                for j in range(N):
                    dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j])
        if max(dist[K-1]) < float("inf"):
            return max(dist[K-1])
        else:
            return -1

import heapq
import collections
class Solution:
    def minimumCost(self, N: int, connections: List[List[int]]) -> int:
        graph = collections.defaultdict(list)
        for a,b,w in connections:
            graph[a].append((b,w))
            graph[b].append((a,w))
        visited,cost = set(),0
        minHeap = [(0,1)]
        while minHeap:
            minCost,city = heapq.heappop(minHeap)
            if city not in visited:
                cost += minCost
                visited.add(city)
                for nxt,c in graph[city]:
                    if nxt not in visited:
                        heapq.heappush(minHeap,(c,nxt))
        return -1 if len(visited) < N else cost

class Solution:
    def minimumCost(self, N: int, connections: List[List[int]]) -> int:
        def find(node,par):
            if par[node] == node:
                return node
            par[node] = find(par[node],par)
            return par[node]
    
        def union(a,b,par,rank1,a_rep,b_rep):
            if rank1[a] == rank1[b]:
                par[a_rep] = b_rep
                rank1[a] += 1
            elif rank1[a] > rank1[b]:
                par[a_rep] = b_rep
            else:
                par[b_rep] = a_rep
                
        parent = [x for x in range(N+1)]
        rank = [1 for i in range(N+1)]
        res,i,e,result = 0,0,0,[]
        graph = sorted(connections,key = lambda x:x[2])
        while i < len(graph) and e < N - 1:
            u,v,w = graph[i]
            uroot,vroot = find(u,parent),find(v,parent)
            if uroot != vroot:
                result.append([u,v])
                res += w
                e += 1
                union(u,v,parent,rank,uroot,vroot)
            i += 1
        if len(result) == N-1:
            return res
        else:
            return -1

from collections import defaultdict
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph,queue,cnt = defaultdict(list),[],0
        inDeg = [0] * numCourses
        for j,i in prerequisites:
            graph[i].append(j)
            inDeg[j] += 1
        for i in range(numCourses):
            if inDeg[i] == 0:
                queue.append(i)
        while queue:
            ele = queue.pop(0)
            for j in graph[ele]:
                inDeg[j] -= 1
                if inDeg[j] == 0:
                    queue.append(j)
            cnt += 1
        if cnt == numCourses:
            return True
        else:
            return False

class Solution:
    def findCircleNum(self, M: List[List[int]]) -> int:
        def find(node,par):
            if par[node] == x:
                return node
            par[node] = find(par[node],par)
            return par[node]

        def union(a,b,par,rank1):
            a_rep,b_rep = find(a,par),find(b,par)
            if rank1[a] == rank1[b]:
                par[a_rep] = b_rep
                rank1[a] += 1
            elif rank1[a] > rank1[b]:
                par[a_rep] = b_rep
            else:
                par[b_rep] = a_rep
        s,V = set(),len(M)
        parent = [x for x in range(V)]
        rank = [1 for i in range(V)]
        for i in range(V):
            for j in range(V):
                if (i != j) and M[i][j] == 1:
                    union(i,j,parent,rank)
        for i in range(V):
            s.add(find(i,parent))
        
        return len(s)

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        n = len(graph)
        adj_table = collections.defaultdict(list)
        for idx,val in enumerate(graph):
            adj_table[idx] = val
        vis = [False for i in range(n)]
        for i in range(n):
            if not vis[i] and adj_table[i]:
                queue = [i]
                vis[i] = 0
                while queue:
                    x = queue.pop(0)
                    for i in adj_table[x]:
                        if not vis[i]:
                            vis[i] = 1 - vis[x]
                            queue.append(i)
                        else:
                            if vis[i] == vis[x]:
                                return False
        return True

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        def is_safe(u, rec_stack):
            if u in visited:
                return u not in rec_stack and u not in unsafe
            visited.add(u)
            rec_stack.add(u)
            for v in graph[u]:
                if not is_safe(v, rec_stack):
                    unsafe.add(u)
                    return False
            rec_stack.remove(u)
            return True
        unsafe, visited = set(), set()
        for u in range(len(graph)):
            if u not in visited: is_safe(u, set())
        return sorted([u for u in range(len(graph)) if u not in unsafe])  

def DFS(graph, v, discovered, parent):
    discovered[v] = True
    for w in graph.adjList[v]:
        if not discovered[w]:
            if DFS(graph, w, discovered, v):
                return True
        elif w != parent: 
            return True
    return False

discovered = [False] * N
DFS(graph, 1, discovered, -1)