Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- from copy import deepcopy
- def makeAdj(arr, n):
- adj = [[] for i in range(n)]
- for i in arr:
- adj[i[0]].append(i[1])
- adj[i[1]].append(i[0])
- return [sorted(i) for i in adj]
- def checkConnectedness(adj):
- used = [False for i in range(len(adj))]
- used[0] = True
- stackDfs = [0]
- while stackDfs:
- point = stackDfs.pop()
- for v in adj[point]:
- if not used[v]:
- stackDfs.append(v)
- used[v] = True
- if False in used:
- return False
- return True
- def getJunctionPoints(adj):
- junctionPoints = []
- used = [False for i in range(len(adj))]
- while False in used:
- tempAdj = deepcopy(adj)
- v = 0
- for i in range(len(used)):
- if not used[i]:
- used[i] = True
- v = i
- break
- tempAdj[v] = []
- for i in range(len(tempAdj)):
- for j in range(len(tempAdj[i])):
- if tempAdj[i][j] == v:
- tempAdj[i].pop(j)
- break
- removeElem = 0
- for i in range(len(tempAdj)):
- if not tempAdj[i]:
- removeElem = i
- break
- tempAdj.pop(removeElem)
- for i in range(len(tempAdj)):
- for j in range(len(tempAdj[i])):
- if tempAdj[i][j] > removeElem:
- tempAdj[i][j] -= 1
- if not checkConnectedness(tempAdj):
- junctionPoints.append(v)
- return junctionPoints
- def getComponents(adj):
- junctionPoints = getJunctionPoints(adj)
- if not junctionPoints:
- return []
- used = [False for i in range(len(adj))]
- for i in junctionPoints:
- used[i] = True
- stackDfs = [junctionPoints[0]]
- component = []
- while "Python is cool":
- if not stackDfs:
- yield component
- if False not in used:
- return
- component = []
- for i in range(len(used)):
- if not used[i]:
- stackDfs.append(i)
- used[i] = True
- point = stackDfs.pop()
- component.append(point)
- for v in adj[point]:
- if not used[v]:
- stackDfs.append(v)
- used[v] = True
- if __name__ == "__main__":
- n = 7
- arr = [(0, 1), (0, 3), (1, 3), (2, 3), (3, 4), (4, 5), (4, 6), (5, 6)]
- adj = makeAdj(arr, n)
- for i in getComponents(adj):
- print(i)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement