​可以访问链接：Q1 题面

附带的 Jupyter 代码文件：【Colab】COMP9312 Project Q1: First Cycle-Causing Edge

A. 题解（中文）

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)

• 对于辅助数组visited，path，father的空间都是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:u=self.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,y=self.find(x),self.find(y)ifx==y:returnifself.size[x]<self.size[y]:x,y=y,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 Edge
Run the cells from top to bottom. Only edit theFirstCycleEdgeQuerycode cell.

1. Code Template

Only 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:u=self.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.pathandroot==self.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, it's not allowedifv==fa: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:fu=self._find(u)fv=self._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.pathreturnNone

2. How to Test Your Code

The 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:req=Request(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()]n=int(lines[0])nums=[]forlineinlines[1:]:nums.extend(map(int,re.findall(r"-?\d+",line)))L=[(nums[i],nums[i+1])foriinrange(0,len(nums),2)]returnn,Ldefparse_expected(text:str)->Optional[Tuple[Tuple[int,int],List[int]]]:value=ast.literal_eval(text.strip())ifisinstance(value,str):value=ast.literal_eval(value)returnvaluedefnormalize_answer(ans:Optional[Tuple[Tuple[int,int],List[int]]]):ifansisNone:returnNoneedge,cycle=ans normalized_edge=tuple(sorted(edge))nodes=cycle[:-1]start=nodes.index(min(nodes))forward=nodes[start:]+nodes[:start]reverse=list(reversed(nodes))start_rev=reverse.index(min(reverse))backward=reverse[start_rev:]+reverse[:start_rev]returnnormalized_edge,tuple(min(forward,backward)),len(cycle)defrun_tests()->None:base_url="https://cgi.cse.unsw.edu.au/~cs9312/26T2/project"test_ids=range(1,4)all_correct=Trueforiintest_ids:print("="*80)print(f"Test{i}")graph_url=f"{base_url}/q1_test_{i}.txt"expected_url=f"{base_url}/q1_test_{i}_expected.txt"graph_text=fetch_text(graph_url)expected_text=fetch_text(expected_url)n,L=parse_graph(graph_text)expected=parse_expected(expected_text)print(f"n ={n}")print(f"|L| ={len(L)}")solver=FirstCycleEdgeQuery()actual=solver.query(n,L)ok=(normalize_answer(actual)==normalize_answer(expected))all_correct=all_correctandok status="CORRECT"ifokelse"INCORRECT"print(f"Output summary:{actual}")print(f"Expected summary:{expected}")print(f"Result:{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 ================================================================================