| 8 | |
| 9 | #class for finding bridge edges |
| 10 | class Graph: |
| 11 | |
| 12 | #basic structure of graph |
| 13 | def __init__(self,vertices): |
| 14 | self.V = vertices |
| 15 | self.graph = defaultdict(list) |
| 16 | self.Time = 0 |
| 17 | self.ans = [] |
| 18 | |
| 19 | #to add a edge |
| 20 | def addEdge(self,u,v): |
| 21 | self.graph[u].append(v) |
| 22 | self.graph[v].append(u) |
| 23 | |
| 24 | #helper function for finding bridge edges |
| 25 | def bridgeUtil(self,u,visited,parent,low,disc): |
| 26 | |
| 27 | visited[u] = True |
| 28 | disc[u] = self.Time |
| 29 | low[u] = self.Time |
| 30 | self.Time +=1 |
| 31 | |
| 32 | for v in self.graph[u]: |
| 33 | |
| 34 | if visited[v] == False: |
| 35 | parent[v] = u |
| 36 | self.bridgeUtil(v,visited,parent,low,disc) |
| 37 | |
| 38 | low[u] = min(low[u],low[v]) |
| 39 | |
| 40 | if(low[v]>disc[u]): |
| 41 | #finally found the bridge edge |
| 42 | self.ans.append([u,v]) |
| 43 | #print(u,v) |
| 44 | |
| 45 | elif v!=parent[u]: |
| 46 | low[u] = min(low[u],disc[v]) |
| 47 | |
| 48 | #function to call helper function with initial inputs |
| 49 | def bridge(self): |
| 50 | |
| 51 | visited = [False] * (self.V) |
| 52 | disc = [float("Inf")] * (self.V) |
| 53 | low = [float("Inf")] * (self.V) |
| 54 | parent = [-1] * (self.V) |
| 55 | |
| 56 | for i in range(self.V): |
| 57 | if visited[i] == False: |
| 58 | self.bridgeUtil(i,visited,parent,low,disc) |
| 59 | |
| 60 | #path function returns parent array |
| 61 | #this function uses dfs for finding the path |
| 62 | #parent arr means for given edge V -- > u in arr[u] = v |
| 63 | |
| 64 | def path(self,x,y): |
| 65 | q = deque() |
| 66 | visited = [False] * (self.V) |
| 67 | q.append(x) |