Submit Info #41385

Problem Lang User Status Time Memory
Cycle Detection pypy3 Tomoyo AC 920 ms 191.90 MiB

ケース詳細
Name Status Time Memory
example_00 AC 52 ms 29.83 MiB
example_01 AC 54 ms 29.87 MiB
example_02 AC 53 ms 29.81 MiB
random_00 AC 734 ms 189.20 MiB
random_01 AC 860 ms 190.68 MiB
random_02 AC 537 ms 149.45 MiB
random_03 AC 152 ms 69.96 MiB
random_04 AC 247 ms 82.12 MiB
random_05 AC 693 ms 171.82 MiB
random_06 AC 559 ms 157.99 MiB
random_07 AC 101 ms 41.34 MiB
random_08 AC 519 ms 145.53 MiB
random_09 AC 322 ms 96.33 MiB
random_dag_00 AC 862 ms 183.81 MiB
random_dag_01 AC 920 ms 191.90 MiB
random_dag_02 AC 521 ms 149.84 MiB
random_dag_03 AC 149 ms 69.71 MiB
random_dag_04 AC 243 ms 81.21 MiB
random_dag_05 AC 767 ms 165.74 MiB
random_dag_06 AC 553 ms 155.60 MiB
random_dag_07 AC 98 ms 41.08 MiB
random_dag_08 AC 613 ms 142.82 MiB
random_dag_09 AC 326 ms 93.79 MiB
random_dag_dense_00 AC 368 ms 94.66 MiB
random_dag_dense_01 AC 220 ms 37.34 MiB
random_dag_dense_02 AC 189 ms 32.21 MiB
random_dag_dense_03 AC 223 ms 37.45 MiB
random_dag_dense_04 AC 374 ms 75.61 MiB
random_dense_00 AC 434 ms 122.78 MiB
random_dense_01 AC 245 ms 43.21 MiB
random_dense_02 AC 196 ms 33.85 MiB
random_dense_03 AC 254 ms 42.35 MiB
random_dense_04 AC 492 ms 112.29 MiB

class Graph: def __init__(self, n, directed=False, decrement=True, destroy=False, edges=[]): self.n = n self.directed = directed self.decrement = decrement self.destroy = destroy self.edges = [set() for _ in range(self.n)] self.parent = [-1]*self.n for x, y in edges: self.add_edge(x,y) def add_edge(self, x, y): if self.decrement: x -= 1 y -= 1 self.edges[x].add(y) if self.directed == False: self.edges[y].add(x) def add_adjacent_list(self, i, adjacent_list): if self.decrement: self.edges[i] = set(map(lambda x: x - 1, adjacent_list)) else: self.edges[i] = set(adjacent_list) def bfs(self, start=None, goal=-1, time=0, save=False): """ :param start: スタート地点 :param goal: ゴール地点 :param save: True = 前回の探索結果を保持する :return: (ループがあっても)最短距離。存在しなければ -1 """ if start is None: start=self.decrement start,goal=start-self.decrement,goal-self.decrement if not save: self.parent = [-1] * self.n p, t = start, time self.parent[p] = -2 next_set = deque([(p, t)]) if p==goal: return t while next_set: p, t = next_set.popleft() for q in self.edges[p]: if q == self.parent[p] and not self.directed: """ 逆流した時の処理 """ continue if self.parent[q] != -1: """ サイクル時の処理 """ continue if q == goal: self.parent[q]=p return t + 1 self.parent[q] = p next_set.append((q, t + 1)) return -1 def connection_counter(self): """ :return: 連結成分の個数。有効グラフではあまり意味がない。 """ cnt = 0 self.parent = [-1] * self.n for start in range(self.n): if self.parent[start] == -1: cnt += 1 self.bfs(start + self.decrement, save=True) return cnt def connection_detail(self): """ :return: 連結成分の(頂点数, 辺の数)。有効グラフではあまり意味がない。 備考: 木であるための必要十分条件は M=N-1 """ ver_edge=[] self.parent = [-1] * self.n for start in range(self.n): if self.parent[start] == -1: ver_cnt, edge_cnt = self._detail(start + self.decrement) ver_edge.append((ver_cnt, edge_cnt)) return ver_edge def _detail(self, start=None): """ :param start: スタート地点 :param save: True = 前回の探索結果を保持する """ if start is None: start=self.decrement start=start-self.decrement p, t = start, 0 self.parent[p] = -2 next_set = deque([(p, t)]) sub_edges,sub_vers = set(),set() while next_set: p, t = next_set.popleft() sub_vers.add(p) for q in self.edges[p]: if q == self.parent[p] and not self.directed: """ 逆流した時の処理 """ continue sub_edges.add((min(p,q),max(p,q))) if self.parent[q] != -1: """ サイクル時の処理 """ continue self.parent[q] = p next_set.append((q, t + 1)) return len(sub_vers),len(sub_edges) def distance_list(self, start=None, save=False): """ :param start: スタート地点 :return: スタート地点から各点への距離のリスト ※ 距離無限大が -1 になっている点に注意!!! """ dist = [-1]*self.n if start is None: start=self.decrement start=start-self.decrement if not save: self.parent = [-1] * self.n p, t = start, 0 self.parent[p] = -2 dist[p] = 0 next_set = deque([(p, t)]) while next_set: p, t = next_set.popleft() for q in self.edges[p]: if q == self.parent[p] and not self.directed: """ 逆流した時の処理 """ continue if self.parent[q] != -1: """ サイクル時の処理 """ continue dist[q] = t + 1 self.parent[q] = p next_set.append((q, t + 1)) return dist def parent_list(self, start=None): """ :return: スタート地点から最短経路で進んだ時の、各頂点の一個前に訪問する頂点番号 訪問しない場合は -1 を返す """ if start is None: start=self.decrement self.distance_list(start) return list(p + self.decrement for p in self.parent[1:]) def most_distant_point(self, start=None, save=False): """ 計算量 O(N) :return: (start から最も遠い頂点, 距離) """ if not save: self.parent = [-1] * self.n if start is None: start=self.decrement start=start-self.decrement res = (start, 0) temp = 0 for i, dist in enumerate(self.distance_list(start+self.decrement, save=save)): if dist > temp: temp = dist res = (i + self.decrement, dist) return res def diameter(self, save=False): """ 計算量 O(N) :return: 木の直径(最も離れた二頂点間の距離)を返す """ if not save: self.parent = [-1] * self.n p = self.most_distant_point(save=save) res = self.most_distant_point(start=p[0], save=save) return res[1] def all_cycle(self): """ 無向グラフ用 O(V(V+E)) """ res=[] for start in range(self.n): flg=0 self.parent = [-1] * self.n p, t = start, 0 self.parent[p] = -2 next_set=deque() starts=set() for q in self.edges[p]: next_set.append((q, t)) self.parent[q]=p starts.add(q) while next_set and flg==0: p, t = next_set.popleft() for q in self.edges[p]: if q == self.parent[p] and not self.directed: """ 逆流した時の処理 """ continue if self.parent[q] != -1: """ サイクル時の処理 """ if q in starts: cycle=[q+self.decrement] r=p while r not in starts: cycle.append(r+self.decrement) r=self.parent[r] if r<0: return -1 cycle.append(r+self.decrement) cycle.append(start+self.decrement) res.append(cycle[::-1]) flg=1 break continue self.parent[q] = p next_set.append((q, t + 1)) return res def minimum_cycle_directed(self): """ 有向グラフ用 O(V(V+E)) """ INF=10**18 dist=[] history=[] for i in range(self.n): dist.append(self.distance_list(start=i+self.decrement,save=False,INF=INF)[:]) history.append(self.parent[:]) res=INF s,g=None,None for i in range(self.n): for j in self.edges[i]: if dist[j][i]+1<res: res=dist[j][i]+1 s,g=i,j if res>=INF: return [] else: self.parent=history[g] return self.path_restoring(g+self.decrement,s+self.decrement) def dfs(self, start=None, goal=-1, time=0, save=False): """ :param start: スタート地点 :param goal: ゴール地点 :param save: True = 前回の探索結果を保持する :return: ゴール地点までの距離。存在しなければ -1。ループがある時は最短距離とは限らないため注意。 """ if start is None: start=self.decrement start,goal=start-self.decrement,goal-self.decrement if not save: self.parent = [-1] * self.n if self.destroy: edges2 = self.edges else: edges2 = [self.edges[p].copy() for p in range(self.n)] parent,directed=self.parent,self.directed p, t = start, time parent[p] = -2 if p==goal: return t while True: if edges2[p]: q = edges2[p].pop() if q == parent[p] and not directed: """ 逆流した時の処理 """ continue if parent[q] != -1: """ サイクルで同一点を訪れた時の処理 """ continue if q == goal: """ ゴール時の処理""" parent[q]=p return t + 1 """ p から q への引継ぎ""" parent[q] = p p, t = q, t + 1 else: """ p から進める点がもう無い時の点 p における処理 """ if p == start and t == time: break p, t = parent[p], t-1 """ 点 p から親ノードに戻ってきた時の親ノードにおける処理 """ return -1 def cycle_detector(self, start=None, time=0, save=False): """ :param p: スタート地点 :param save: True = 前回の探索結果を保持する(遅い) :return: サイクルリストを返す。存在しない場合は [] """ if start is None: start=self.decrement start=start-self.decrement if not save: self.parent = [-1] * self.n self.finished=[0]*self.n edges2=self.edges p, t = start, time self.parent[p] = -2 history = [p+self.decrement] cycle = [] while True: if edges2[p]: q = edges2[p].pop() if q == self.parent[p] and not self.directed: """ 逆流した時の処理 """ """""""""""""""""""" continue if self.parent[q] != -1: """ サイクルで同一点を訪れた時の処理 """ if not self.finished[q] and not cycle: cycle_start=history.index(q+self.decrement) if save==False: return history[cycle_start:] else: cycle = history[cycle_start:] """""""""""""""""""" continue """ p から q への引継ぎ""" """""""""""""""""""" history.append(q+self.decrement) self.parent[q] = p p, t = q, t + 1 else: """ p から進める点がもう無い時の点 p における処理 """ self.finished[p]=1 history.pop() """""""""""""""""""" if p == start and t == time: break p, t = self.parent[p], t-1 """ 点 p から親ノードに戻ってきた時の親ノードにおける処理 """ """""""""""""""""""" return cycle def tree_counter(self, detail=False): """ :param detail: True = サイクルのリストを返す :return: 木(閉路を含まない)の個数を返す """ self.parent = [-1] * self.n self.finished=[0]*self.n connection_number = 0 cycle_list = [] for p in range(self.n): if self.parent[p] == -1: connection_number += 1 cycle = self.cycle_detector(p + self.decrement, save=True) if cycle: return cycle return [] def path_detector(self, start=None, time=0, save=False): """ :param p: スタート地点 :param save: True = 前回の探索結果を保持する :return: 各点までの距離と何番目に発見したかを返す """ if start is None: start=self.decrement start=start-self.decrement if not save: self.parent = [-1] * self.n edges2= [] for i in range(self.n): edges2.append(sorted(self.edges[i], reverse=True)) p, t = start, time self.parent[p] = -2 full_path = [(p + self.decrement,t)] while True: if edges2[p]: q = edges2[p].pop() if q == self.parent[p] and not self.directed: """ 逆流した時の処理 """ """""""""""""""""""" continue if self.parent[q] != -1: """ サイクルで同一点を訪れた時の処理 """ """""""""""""""""""" continue """ p から q への引継ぎ""" """""""""""""""""""" self.parent[q] = p p, t = q, t + 1 full_path.append((p + self.decrement, t)) else: """ p から進める点がもう無い時の点 p における処理 """ """""""""""""""""""" if p == start and t == time: break p, t = self.parent[p], t-1 """ 点 p から親ノードに戻ってきた時の親ノードにおける処理 """ full_path.append((p + self.decrement, t)) """""""""""""""""""" return full_path def path_list(self): """ :return: 探索経路を返す。 """ self.parent = [-1]*self.n res = [] for p in range(self.n): if self.parent[p] == -1: res.append(self.path_detector(p + self.decrement, time=1, save=True)) return res def path_restoring(self,start,goal): start,goal=start-self.decrement,goal-self.decrement q=goal res=[] while q!=start: res.append(q+self.decrement) q=self.parent[q] if q<0: return -1 res.append(start+self.decrement) return res[::-1] def draw(self): """ :return: グラフを可視化 """ import matplotlib.pyplot as plt import networkx as nx if self.directed: G = nx.DiGraph() else: G = nx.Graph() for x in range(self.n): for y in self.edges[x]: G.add_edge(x + self.decrement, y + self.decrement) pos = nx.spring_layout(G) nx.draw_networkx(G, pos, connectionstyle='arc3, rad = 0.1') plt.axis("off") plt.show() ################################################################################################## def make_graph(N_min=2, N_max=5, M_min=1, M_max=10, directed=False,decrement=True): """ 自己ループの無いグラフを生成。N>=2 :param directed: True = 有効グラフ :param decrement: True = 1-indexed :return: """ import random input_data = [] global input N=random.randint(N_min,N_max,) if N>2: M_max2=(3*N-6)*(1+directed) else: M_max2=1 M=random.randint(max(1,M_min),min(M_max,M_max2)) print("#########") edges=set() for _ in range(1,M+1): edge=random.sample(range(decrement,N+decrement),2) if directed==False: edge.sort() edge=tuple(edge) if edge not in edges: edges.add(edge) print(N,len(edges)) input_data.append(" ".join(map(str,(N,len(edges))))) for edge in edges: print(*edge) input_data.append(" ".join(map(str,edge))) print("#########") input_data=iter(input_data) input = lambda: next(input_data) def draw(N,edges,decrement=1): import matplotlib.pyplot as plt import networkx as nx G=nx.Graph() for x in range(N): for y in edges[x]: G.add_edge(x+decrement,y+decrement) pos=nx.spring_layout(G) nx.draw_networkx(G,pos) plt.axis("off") plt.show() ###################################################################### def example(): global input example=iter( """ 1000 0 """ .strip().split("\n")) input=lambda:next(example) ###################################################################### import sys input=sys.stdin.readline from collections import deque # example() # make_graph(N_min=7,N_max=7,M_min=10,M_max=10,directed=True) N, M = map(int, input().split()) G = Graph(N, directed=True, decrement=False, destroy=False) d=dict() for i in range(M): x, y = map(int, input().split()) G.add_edge(x, y) d[(x,y)]=i cycles=G.tree_counter(detail=True) if not cycles: print(-1) else: res=[] for i in range(len(cycles)): a,b=cycles[i],cycles[(i+1)%len(cycles)] res.append(str(d[a,b])) print(len(res)) print("\n".join(res))