#677815 (PyPy3) No.1565 Union

提出ソース
結果

問題	No.1565 Union
ユーザー	None
提出日時	2021-07-13 09:22:36
言語	PyPy3 (7.3.15)
結果	AC
実行時間	523 ms / 2,000 ms
コード長	19,862 bytes
コンパイル時間	200 ms
コンパイル使用メモリ	81,828 KB
実行使用メモリ	137,932 KB
最終ジャッジ日時	2023-12-19 13:19:14
合計ジャッジ時間	8,498 ms
ジャッジサーバーID （参考情報）	judge11 / judge14
このコードへのチャレンジ（β）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	45 ms 57,656 KB
testcase_01	AC	47 ms 57,656 KB
testcase_02	AC	46 ms 57,656 KB
testcase_03	AC	45 ms 57,656 KB
testcase_04	AC	47 ms 57,656 KB
testcase_05	AC	45 ms 57,656 KB
testcase_06	AC	46 ms 57,656 KB
testcase_07	AC	47 ms 57,656 KB
testcase_08	AC	48 ms 57,656 KB
testcase_09	AC	47 ms 57,656 KB
testcase_10	AC	161 ms 84,184 KB
testcase_11	AC	306 ms 116,660 KB
testcase_12	AC	283 ms 95,460 KB
testcase_13	AC	146 ms 87,192 KB
testcase_14	AC	363 ms 106,788 KB
testcase_15	AC	523 ms 131,276 KB
testcase_16	AC	389 ms 128,716 KB
testcase_17	AC	517 ms 131,404 KB
testcase_18	AC	501 ms 131,404 KB
testcase_19	AC	510 ms 131,404 KB
testcase_20	AC	227 ms 136,908 KB
testcase_21	AC	228 ms 137,548 KB
testcase_22	AC	230 ms 137,036 KB
testcase_23	AC	228 ms 137,676 KB
testcase_24	AC	231 ms 137,804 KB
testcase_25	AC	257 ms 137,932 KB
testcase_26	AC	255 ms 137,932 KB
testcase_27	AC	253 ms 137,932 KB
testcase_28	AC	260 ms 137,804 KB
testcase_29	AC	250 ms 137,932 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
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
        if self.destroy:
            edges2 = self.edges
        else:
            edges2 = [self.edges[p].copy() for p in range(self.n)]

        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.destroy=True # これをしないと計算量が壊れる
        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:
                    cycle_list.append(cycle)
        if not detail:
            return connection_number - len(cycle_list)
        else:
            return cycle_list

    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_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_tree(N=10,show=True,decrement=1):
    global input

    # decrement=True: create 1-indexed tree

    def find(x):
        tmp=[]
        while parents[x]>=0:
            tmp.append(x)
            x=parents[x]
        for y in tmp: parents[y]=x
        return x

    def union(x,y):
        x,y=find(x),find(y)
        if x==y: return
        if parents[x]>parents[y]: x,y=y,x
        parents[x]+=parents[y]
        parents[y]=x

    def same(x,y):
        return find(x)==find(y)

    import random
    # N = random.randint(2, N)
    parents=[-1]*N
    edges=[]
    input_data=[]
    input_data.append(str(N))
    for i in range(N-1):
        while True:
            j=random.randint(0,N-1)
            if same(i,j): continue
            union(i,j)
            edges.append((i+decrement,j+decrement))

            break

    for i,j in edges:
        input_data.append(" ".join(map(str,(i,j))))
    input_data=iter(input_data)
    input=lambda:next(input_data)


    if show:
        print("#######################")
        print(N)
        for p in edges:
            print(*p)
        print("#######################")
    return edges

def example_special_tree(N, type, show=True, decrement=1):
    global input

    edges = []

    if type=="path":
        for i in range(N-1):
            edges.append((i+decrement,i+1+decrement))
    if type=="star":
        for i in range(N-1):
            edges.append((i,i+1+decrement))
    if type=="binary":
        i = 1
        while True:
            if (i<<1) >= N: break
            edges.append((i-1+decrement, (i<<1)-1+decrement))
            if (i<<1)+1 >= N: break
            edges.append((i-1+decrement, (i<<1)+decrement))
            i += 1

    input_data=[]
    input_data.append(str(N))

    for i,j in edges:
        input_data.append(" ".join(map(str,(i,j))))
    input_data=iter(input_data)
    input=lambda:next(input_data)

    if show:
        print("#######################")
        print(N)
        for p in edges:
            print(*p)
        print("#######################")
    return edges

def example():
    global input
    example=iter(
        """
6 9
1 2
2 3
3 4
4 5
5 6
5 1
5 2
6 1
6 2


        """
            .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=False, decrement=False, destroy=False)
for _ in range(M):
    x, y = map(int, input().split())
    x-=1
    y-=1
    G.add_edge(x, y)

d=G.distance_list(start=0)
print(d[-1])
yukicoder

結果

テストケース

ソースコード
