​可以访问链接Q1 题面附带的 Jupyter 代码文件【Colab】COMP9312 Project Q1: First Cycle-Causing EdgeA. 题解中文1. 复杂度分析时间复杂度O ( m × α ( n ) n ) O(m\times \alpha(n)n)O(m×α(n)n)并查集查找和合并的时间复杂度是α ( n ) \alpha(n)α(n)每遍历一条边就要对边的两个端点进行并查集所以为O ( m × α ( n ) ) O(m \times \alpha(n))O(m×α(n))最后 DFS 找环的时候最坏情况下把所有点都遍历一次时间复杂度为O ( n ) O(n)O(n).综上时间复杂度为O ( m × α ( n ) n ) O(m\times \alpha(n)n)O(m×α(n)n).空间复杂度O ( n ) O(n)O(n)对于辅助数组visitedpathfather的空间都是O ( n ) O(n)O(n)对于邻接表的空间本质上是对每条边的两个端点储存也就是O ( m ) O(m)O(m)。在本题中边数要小于顶点数即O ( m ) ≤ O ( n ) O(m) \le O(n)O(m)≤O(n)综上空间复杂度为O ( n ) O(n)O(n).2. 解题思路我们的核心任务只用解决两个问题如何判断存在一个环如何找到这个环的路径2.1 并查集判断环对于第一个问题我们可以使用并查集来判断环的存在。首先我们设置一个父节点father用来储存每个节点的祖父如果一条边的两个端点u , v u,vu,v的祖父相同即代表他们是在一个环中如果一条边的两个端点u , v u,vu,v祖父不同我们便将他们的祖父统一为同一个。这里我们就涉及到了两个并查集中的经典操作查询父节点其中最为常见的优化操作为路径压缩。当我在本科阶段参加ICPC竞赛的时候我曾看到过一种循环路径压缩的写法相比于递归写法它可以更好避免栈溢出。def_find(self,u:int)-int:# path compression# This is a neat coding trick I figured out for DSU path compression when competing in ICPC contests :)whileself.father[u]!u:uself.father[u]self.father[self.father[u]]returnu合并节点关于合并节点同样存在一个优化即启发式合并按秩合并。根据 Tarjan 在 1975 年发布的 A Linear-Time Algorithm for a Special Case of Disjoint Set Union. 可知当并查集中使用路径压缩与按秩合并并查集的每个操作平均时间为O ( α ( n ) ) O(\alpha(n))O(α(n)).defunite(self,x,y):x,yself.find(x),self.find(y)ifxy:returnifself.size[x]self.size[y]:x,yy,x self.pa[y]x self.size[x]self.size[y]2.2 DFS遍历环的路径以结点root为开端进行 dfs 遍历每一条路径直到找出一条尾端点为root结点的路径说明形成了一个环。实现思路就是常规的 dfs 算法与回溯算法但是针对于这个题目有如下需要注意的点当发现此时再次走到开始端点root说明形成一个环结束递归当发现走到一个已经访问过的非开始节点说明走错路了返回 False 退出递归当发现下一个走的节点是当前结点的来时结点例如从结点u uu走到了结点v vv结果结点v vv的下一个结点要访问u uu时返回 Flase 退出递归当发现 dfs 的返回值为False的时候开始回溯同时清除此时路径的尾节点B. 题解英文施工中… …C. Jupyter 代码​# COMP9312 Project Q1: First Cycle-Causing EdgeRun the cells from top to bottom. Only edit theFirstCycleEdgeQuerycode cell.1. Code TemplateOnly edit this cell. ImplementFirstCycleEdgeQuery.query(n, L). You may add helper methods or fields inside the class, but do not change the public class name or method signature.################################################################################# You can import any Python Standard Library modules.fromtypingimportList,Optional,Tuple################################################################################classFirstCycleEdgeQuery: First cycle-causing edge query. You may add helper methods and fields inside this class, but do not change the public signature of query(). def__init__(self):# Initially, every vertex takes itself as its parent node.self.father[]# store the graphself.graph[[]]self.path[]self.visited[]def_find(self,u:int)-int:# path compression# This is a neat coding trick I figured out for DSU path compression when competing in ICPC contests :)whileself.father[u]!u:uself.father[u]self.father[self.father[u]]returnudef_merge(self,fu:int,fv:int)-None:self.father[fv]fudef_dfs(self,root:int,fa:int)-bool: Use recursive DFS to traverse paths originating from the root vertex. If a path whose head vertex is equal to its tail vertex is found, a cycle exists. # A cycle is generated if the initial vertex and the terminal vertex are the same.ifself.pathandrootself.path[0]:self.path.append(root)returnTrue# Do not revisit visited vertices except the starting point.ifself.visited[root]:returnFalseself.visited[root]Trueself.path.append(root)forvinself.graph[root]:# i.e. 4 - 5 - 4, its not allowedifvfa:continueifself._dfs(v,root):# If a cycle is constructed, return True and exit the recursive call.returnTrueelse:# Delete the vertex on the path when the path fails to construct a cycle.self.path.pop()returnFalsedefquery(self,n:int,L:List[Tuple[int,int]],)-Optional[Tuple[Tuple[int,int],List[int]]]: Return the first cycle-causing edge and the cycle containing it. Parameters ---------- n: The number of vertices in the undirected graph. Vertex IDs range from 0 to n - 1. L: The edge insertion stream. Each edge is a tuple (u, v). Returns ------- If a first cycle-causing edge (u, v) exists, return: [[u, v], [i, ..., j]] The order does not matter. If no inserted edge creates a cycle, return None. # TODO: implement your solution here.self.father[iforiinrange(n)]self.graph[[]foriinrange(n)]#Store the graph with an adjacency list.self.visited[Falseforiinrange(n)]# Use DSU to judge whether a cycle exists.foru,vinL:fuself._find(u)fvself._find(v)self.graph[u].append(v)self.graph[v].append(u)iffu!fv:self._merge(fu,fv)else:ifself._dfs(u,-1):return(u,v),self.pathreturnNone2. How to Test Your CodeThe following tests use theFirstCycleEdgeQueryclass defined above. Do not edit this cell. Each test prints the input, your output, the expected output, the running time, and whether the result is correct.################################################################################# Do not edit this code cell.fromurllib.requestimporturlopen,Requestimportastimportre################################################################################deffetch_text(url:str)-str:reqRequest(url,headers{User-Agent:Mozilla/5.0})withurlopen(req)asresponse:returnresponse.read().decode(utf-8).strip()defparse_graph(text:str)-Tuple[int,List[Tuple[int,int]]]:lines[line.strip()forlineintext.splitlines()ifline.strip()]nint(lines[0])nums[]forlineinlines[1:]:nums.extend(map(int,re.findall(r-?\d,line)))L[(nums[i],nums[i1])foriinrange(0,len(nums),2)]returnn,Ldefparse_expected(text:str)-Optional[Tuple[Tuple[int,int],List[int]]]:valueast.literal_eval(text.strip())ifisinstance(value,str):valueast.literal_eval(value)returnvaluedefnormalize_answer(ans:Optional[Tuple[Tuple[int,int],List[int]]]):ifansisNone:returnNoneedge,cycleans normalized_edgetuple(sorted(edge))nodescycle[:-1]startnodes.index(min(nodes))forwardnodes[start:]nodes[:start]reverselist(reversed(nodes))start_revreverse.index(min(reverse))backwardreverse[start_rev:]reverse[:start_rev]returnnormalized_edge,tuple(min(forward,backward)),len(cycle)defrun_tests()-None:base_urlhttps://cgi.cse.unsw.edu.au/~cs9312/26T2/projecttest_idsrange(1,4)all_correctTrueforiintest_ids:print(*80)print(fTest{i})graph_urlf{base_url}/q1_test_{i}.txtexpected_urlf{base_url}/q1_test_{i}_expected.txtgraph_textfetch_text(graph_url)expected_textfetch_text(expected_url)n,Lparse_graph(graph_text)expectedparse_expected(expected_text)print(fn {n})print(f|L| {len(L)})solverFirstCycleEdgeQuery()actualsolver.query(n,L)ok(normalize_answer(actual)normalize_answer(expected))all_correctall_correctandok statusCORRECTifokelseINCORRECTprint(fOutput summary:{actual})print(fExpected summary:{expected})print(fResult:{status})print(*80)run_tests() Test 1 n 6 |L| 6 Output summary: ((5, 0), [5, 4, 3, 2, 1, 0, 5]) Expected summary: [[5, 0], [5, 4, 3, 2, 1, 0, 5]] Result: CORRECT Test 2 n 5 |L| 3 Output summary: None Expected summary: None Result: CORRECT Test 3 n 10680 |L| 24316 Output summary: ((4, 5), [4, 3, 5, 4]) Expected summary: [[4, 5], [4, 3, 5, 4]] Result: CORRECT