Last active
January 19, 2021 21:51
-
-
Save adamgarcia4/8aaaa4297e54005370cd955792556684 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| from collections import defaultdict | |
| def getAdjList(numNodes, fromList, toList): | |
| adjList = [[] for _ in range(numNodes + 1)] | |
| for u, v in zip(fromList, toList): | |
| adjList[u].append(v) | |
| adjList[v].append(u) | |
| return adjList | |
| ''' | |
| at: Current Node that I am at | |
| parent: Node from which I came (used to eliminate bidirectional cycles) | |
| partial: array that stores path up to this point. (used to check size of cycle). | |
| adjList: The graph | |
| visited: Boolean Visited Array (used to check for cycle) | |
| ''' | |
| # Explores up to a depth of 3. Then on the third, we check to see if it forms a cycle. | |
| def visit(at, parent, partial, adjList, visited, allTrios): | |
| # Unit of work to be done at this node | |
| visited[at] = True | |
| partial.append(at) | |
| # Explore all neighbors | |
| for to in adjList[at]: | |
| # Skip bidirectional cycle. | |
| # Removing cycle of length 2. | |
| if to == parent: | |
| continue | |
| # If currDepth is 3, then ONLY check for cycle. | |
| if len(partial) == 3: | |
| if visited[to]: | |
| allTrios.add(tuple(sorted(partial))) | |
| continue | |
| # Partial is less than 3. | |
| visit(to, at, partial, adjList, visited, allTrios) | |
| # Backtracking work to be done | |
| partial.pop() | |
| visited[at] = False | |
| def getTrios(numNodes, fromList, toList): | |
| adjList = getAdjList(numNodes, fromList, toList) | |
| visited = [False] * (numNodes + 1) | |
| allTrios = set() | |
| for node in range(1, numNodes + 1): | |
| if not visited[node]: | |
| visit(node, -1, [], adjList, visited, allTrios) | |
| return allTrios, adjList | |
| def getCycles(numNodes, fromList, toList): | |
| allTrios, adjList = getTrios(numNodes, fromList, toList) | |
| # print('allTrios', list(allTrios)) | |
| globalMin = float('inf') | |
| for trio in allTrios: | |
| minScore = -6 | |
| for num in trio: | |
| minScore += len(adjList[num]) | |
| globalMin = min(globalMin, minScore) | |
| return globalMin if globalMin != float('inf') else -1 | |
| tests = [ | |
| { | |
| "numNodes": 6, | |
| "fromList": [1,2,2,3,4,5], | |
| "toList": [2,4,5,5,5,6], | |
| "ans": 3 | |
| }, | |
| { | |
| "numNodes": 5, | |
| "fromList": [1,1,2,2,3,4], | |
| "toList": [2,3,3,4,4,5], | |
| "ans": 2 | |
| }, | |
| ] | |
| for test in tests: | |
| ans = getCycles(test["numNodes"], test["fromList"], test["toList"]) | |
| print(ans) | |
| assert(ans == test["ans"]) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment