In this problem, a tree is an undirected graph that is connected and has no cycles.
The given input is a graph that started as a tree with N nodes (with distinct values 1, 2, ..., N), with one additional edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.
The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] with u < v, that represents an undirected edge connecting nodes u and v.
Return an edge that can be removed so that the resulting graph is a tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array. The answer edge [u, v] should be in the same format, with u < v.
Example 1:
Input: [[1,2], [1,3], [2,3]] Output: [2,3] Explanation: The given undirected graph will be like this: 1 / 2 - 3
Example 2:
Input: [[1,2], [2,3], [3,4], [1,4], [1,5]]
Output: [1,4]
Explanation: The given undirected graph will be like this:
5 - 1 - 2
| |
4 - 3
1. 1st use union-find method. find the group of each connected node. and check new connected edge to be in the previous group
#initialize tree
def constructUnion(N): #union-size
for i in range(1, N+1):
idLst[i] = i
sizeLst[i] = 1
#find group id
def find(p):
while(p != idLst[p]):
idLst[p] = idLst[idLst[p]]
p = idLst[p]
return p
# check whether they are connected
def isConnected(p, q):
return find(p) == find(q)
#Union two element into same group
def union(p, q):
idp = find (p)
idq = find(q)
if idp !=idq:
if sizeLst[p] > sizeLst[q]:
idLst[idq] = idp
sizeLst[idp] += sizeLst[idq]
else:
idLst[idp] = idq
sizeLst[idq] += sizeLst[idp]
N = 1000
idLst = [0] * (N+1)
sizeLst = [0] * (N+1)
constructUnion(N)
for eg in edges:
if isConnected(eg[0], eg[1]): return eg
#print ("pair for cycle : ", eg)
union(eg[0], eg[1])
return []
--reference: https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf
2. use naive way to detect the cycle exist or not in the graph
def cycleIterative(v, visited, parent, gTmp):
visited[v] = True
for i in gTmp[v]:
if not visited[i]:
if cycleIterative(i, visited, v, gTmp):
return True
elif parent != i:
return True
return False
g = defaultdict(list) # default dictionary to store graph
for edge in edges:
g[edge[0]].append(edge[1])
g[edge[1]].append(edge[0])
def cycle(gTmp):
visited = defaultdict()
for v in gTmp:
visited[v] = False
for v in gTmp:
if not visited[v]:
if cycleIterative(v, visited, -1, gTmp):
return True
return False
for pair in edges[::-1]:
gTmp = deepcopy(g)
#remove the pair edge from g
gTmp[pair[0]].remove(pair[1])
gTmp[pair[1]].remove(pair[0])
print ("edge: ", gTmp)
if not cycle(gTmp):
print ("pair for cycle : ", pair)
return []