#950301 (PyPy3) No.1254 補強への架け橋

提出ソース

結果

問題	No.1254 補強への架け橋
ユーザー	👑 Kazun
提出日時	2024-02-12 10:57:48
言語	PyPy3 (7.3.15)
結果	AC
実行時間	426 ms / 2,000 ms
コード長	8,571 bytes
コンパイル時間	332 ms
コンパイル使用メモリ	81,700 KB
実行使用メモリ	130,032 KB
最終ジャッジ日時	2024-02-12 10:58:20
合計ジャッジ時間	30,417 ms
ジャッジサーバーID （参考情報）	judge11 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	41 ms 55,604 KB
testcase_01	AC	41 ms 55,600 KB
testcase_02	AC	40 ms 55,600 KB
testcase_03	AC	40 ms 55,600 KB
testcase_04	AC	40 ms 55,600 KB
testcase_05	AC	41 ms 55,600 KB
testcase_06	AC	42 ms 55,604 KB
testcase_07	AC	41 ms 55,600 KB
testcase_08	AC	42 ms 55,604 KB
testcase_09	AC	42 ms 55,604 KB
testcase_10	AC	41 ms 55,600 KB
testcase_11	AC	40 ms 55,604 KB
testcase_12	AC	40 ms 55,600 KB
testcase_13	AC	42 ms 57,676 KB
testcase_14	AC	42 ms 57,676 KB
testcase_15	AC	41 ms 55,600 KB
testcase_16	AC	42 ms 55,604 KB
testcase_17	AC	42 ms 55,604 KB
testcase_18	AC	42 ms 55,604 KB
testcase_19	AC	41 ms 55,604 KB
testcase_20	AC	41 ms 57,676 KB
testcase_21	AC	44 ms 55,604 KB
testcase_22	AC	42 ms 55,604 KB
testcase_23	AC	41 ms 55,604 KB
testcase_24	AC	42 ms 57,676 KB
testcase_25	AC	41 ms 55,600 KB
testcase_26	AC	43 ms 57,676 KB
testcase_27	AC	42 ms 55,600 KB
testcase_28	AC	42 ms 57,676 KB
testcase_29	AC	41 ms 55,600 KB
testcase_30	AC	41 ms 55,604 KB
testcase_31	AC	43 ms 57,676 KB
testcase_32	AC	41 ms 55,600 KB
testcase_33	AC	42 ms 57,676 KB
testcase_34	AC	42 ms 57,676 KB
testcase_35	AC	42 ms 57,676 KB
testcase_36	AC	42 ms 57,676 KB
testcase_37	AC	43 ms 57,676 KB
testcase_38	AC	42 ms 57,676 KB
testcase_39	AC	41 ms 55,604 KB
testcase_40	AC	42 ms 57,676 KB
testcase_41	AC	42 ms 55,600 KB
testcase_42	AC	41 ms 55,604 KB
testcase_43	AC	74 ms 74,440 KB
testcase_44	AC	47 ms 57,672 KB
testcase_45	AC	49 ms 57,672 KB
testcase_46	AC	66 ms 72,604 KB
testcase_47	AC	49 ms 59,728 KB
testcase_48	AC	66 ms 72,784 KB
testcase_49	AC	44 ms 57,676 KB
testcase_50	AC	78 ms 76,588 KB
testcase_51	AC	76 ms 74,936 KB
testcase_52	AC	78 ms 76,588 KB
testcase_53	AC	62 ms 70,368 KB
testcase_54	AC	72 ms 73,880 KB
testcase_55	AC	67 ms 72,724 KB
testcase_56	AC	44 ms 57,676 KB
testcase_57	AC	64 ms 70,704 KB
testcase_58	AC	57 ms 68,288 KB
testcase_59	AC	42 ms 57,676 KB
testcase_60	AC	45 ms 57,672 KB
testcase_61	AC	67 ms 72,728 KB
testcase_62	AC	43 ms 57,676 KB
testcase_63	AC	146 ms 80,776 KB
testcase_64	AC	124 ms 78,504 KB
testcase_65	AC	143 ms 79,084 KB
testcase_66	AC	140 ms 78,872 KB
testcase_67	AC	114 ms 77,944 KB
testcase_68	AC	133 ms 79,004 KB
testcase_69	AC	132 ms 79,644 KB
testcase_70	AC	126 ms 78,368 KB
testcase_71	AC	119 ms 78,232 KB
testcase_72	AC	145 ms 80,136 KB
testcase_73	AC	128 ms 78,240 KB
testcase_74	AC	132 ms 79,368 KB
testcase_75	AC	130 ms 78,748 KB
testcase_76	AC	99 ms 77,592 KB
testcase_77	AC	133 ms 78,484 KB
testcase_78	AC	148 ms 80,248 KB
testcase_79	AC	145 ms 80,392 KB
testcase_80	AC	139 ms 80,016 KB
testcase_81	AC	148 ms 80,528 KB
testcase_82	AC	154 ms 80,136 KB
testcase_83	AC	424 ms 129,364 KB
testcase_84	AC	366 ms 126,644 KB
testcase_85	AC	300 ms 107,996 KB
testcase_86	AC	355 ms 119,712 KB
testcase_87	AC	376 ms 124,572 KB
testcase_88	AC	165 ms 82,708 KB
testcase_89	AC	426 ms 128,848 KB
testcase_90	AC	300 ms 109,752 KB
testcase_91	AC	251 ms 102,720 KB
testcase_92	AC	185 ms 89,248 KB
testcase_93	AC	328 ms 117,932 KB
testcase_94	AC	325 ms 114,420 KB
testcase_95	AC	305 ms 113,764 KB
testcase_96	AC	400 ms 125,124 KB
testcase_97	AC	223 ms 95,468 KB
testcase_98	AC	387 ms 124,808 KB
testcase_99	AC	269 ms 105,680 KB
testcase_100	AC	403 ms 130,032 KB
testcase_101	AC	179 ms 87,696 KB
testcase_102	AC	151 ms 81,692 KB
testcase_103	AC	180 ms 88,972 KB
testcase_104	AC	198 ms 94,124 KB
testcase_105	AC	333 ms 117,940 KB
testcase_106	AC	226 ms 99,796 KB
testcase_107	AC	389 ms 129,548 KB
testcase_108	AC	398 ms 129,404 KB
testcase_109	AC	333 ms 118,612 KB
testcase_110	AC	319 ms 113,412 KB
testcase_111	AC	314 ms 115,548 KB
testcase_112	AC	202 ms 93,300 KB
testcase_113	AC	317 ms 112,972 KB
testcase_114	AC	226 ms 96,784 KB
testcase_115	AC	160 ms 82,932 KB
testcase_116	AC	247 ms 103,252 KB
testcase_117	AC	186 ms 91,396 KB
testcase_118	AC	406 ms 125,540 KB
testcase_119	AC	270 ms 105,928 KB
testcase_120	AC	370 ms 123,516 KB
testcase_121	AC	179 ms 90,212 KB
testcase_122	AC	273 ms 103,008 KB
testcase_123	AC	40 ms 55,604 KB
testcase_124	AC	391 ms 118,892 KB
testcase_125	AC	396 ms 118,624 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

class Graph:
    __slots__=("edge_offset", "edge_alive", "edge_ids", "vertex_alive", "adjacent", "deg")

    #入力定義
    def __init__(self, N = 0, edge_offset = 0):
        """ N 頂点の空グラフ (多重辺なし) を生成する."""

        self.adjacent = [[] for _ in range(N)]
        self.edge_ids = [[] for _ in range(N)]
        self.vertex_alive = [1] * N

        self.edge_offset = edge_offset
        self.edge_alive = [0] * edge_offset

        self.deg = [0] * N


    #頂点の追加
    def add_vertex(self):
        """ 頂点を追加する.

        """

        self.adjacent.append([])
        self.edge_ids.append([])
        self.vertex_alive.append(1)
        self.deg.append(0)

        return self.order() - 1

    def add_vertices(self, k):
        """ 頂点を k 個追加する.

        k: int
        """

        n=self.order()

        self.adjacent.extend([[] for _ in range(k)])
        self.edge_ids.extend([[] for _ in range(k)])
        self.vertex_alive.extend([1] * k)
        self.deg.extend([0] * k)

        return list(range(n, n + k))

    #辺の追加
    def add_edge(self, u, v):
        """ 無向辺 uv を加える"""

        j = len(self.edge_alive)

        self.adjacent[u].append(v)
        self.adjacent[v].append(u)

        self.edge_ids[u].append(j)
        self.edge_ids[v].append(j)

        self.deg[u] += 1; self.deg[v] += 1

        self.edge_alive.append(1)

        return j

    #辺を除く
    def remove_edge(self,u,v):
        """ 無向辺 uv が存在するならば除く"""
        pass

    def reset_vertex(self, u):
        """ 頂点 u に接続している辺を全て消す."""
        pass

    #Walkの追加
    def add_walk(self, *walk):
        """ walk=(w[0],...,w[n-1]) に対して, n-1 本の辺 w[i]w[i+1] を加える."""
        for i in range(len(walk) - 1):
            self.add_edge(walk[i], walk[i + 1])

    #Cycleの追加
    def add_cycle(self, *cycle):
        """ cycle=(c[0], ..., c[n-1]) を加える. """
        self.add_walk(*cycle)
        self.add_edge(cycle[-1], cycle[0])

    #グラフに辺が存在するか否か
    def edge_exist(self, u, v):
        """ 辺 uv が存在するか? """
        pass

    def partner(self, v):
        adj = self.adjacent[v]
        edge_ids = self.edge_ids[v]
        return [adj[k] for k in range(len(edge_ids)) if self.edge_alive[edge_ids[k]]]

    def partner_with_index(self, v):
        adj = self.adjacent[v]
        edge_ids = self.edge_ids[v]
        return [(adj[k], edge_ids[k]) for k in range(len(edge_ids)) if self.edge_alive[edge_ids[k]]]

    #近傍
    def neighborhood(self, v):
        """ 頂点 v  の近傍を求める. """

        adj = self.adjacent[v]
        edge_ids = self.edge_ids[v]
        return list(set(adj[k] for k in range(len(edge_ids)) if self.edge_alive[edge_ids[k]]))

    #次数
    def degree(self, v):
        """ 頂点 v の次数を求める. """
        return self.deg[v]

    #頂点数
    def vertex_count(self):
        """ グラフの頂点数 (位数) を出力する. """
        return len(self.adjacent)

    def order(self):
        """ グラフの位数 (頂点数) を出力する. """
        return len(self.adjacent)

    #辺数
    def edge_count(self):
        """ 辺の本数 (サイズ) を出力する."""

        return len(self.edge_alive) - self.edge_offset

    def size(self):
        """ サイズ (辺の本数) を出力する. """

        return len(self.edge_alive) - self.edge_offset

    #頂点vを含む連結成分
    def connected_component(self, v):
        """ 頂点 v を含む連結成分を出力する."""

        N = self.order()

        stack = [v]
        comp = [0] * N; comp[v] = 1
        while stack:
            x = stack.pop()
            for y in self.neighborhood(x):
                if comp[y] == 0:
                    comp[y] = 1
                    stack.append(y)

        return [x for x in range(N) if comp[x]]

    #距離
    def distance(self, u, v, default):
        """ 2頂点 u,v 間の距離を求める."""

        if u == v:
            return 0

        from collections import deque

        N = self.order()
        dist = [-1] * N; dist[u]=0

        queue = deque([u])
        while queue:
            x = queue.popleft()
            for y in self.neighborhood(x):
                if dist[y] == -1:
                    dist[y] = dist[x] + 1
                    queue.append(y)

                    if y == v:
                        return dist[v]

        return default

    #ある1点からの距離
    def distance_all(self,u,default=-1):
        """ 頂点 u からの距離を求める."""

        from collections import deque

        N = self.order()
        dist = [-1] * N; dist[u]=0

        queue = deque([u])
        while queue:
            x = queue.popleft()
            for y in self.neighborhood(x):
                if dist[y] == -1:
                    dist[y] = dist[x] + 1
                    queue.append(y)

        return [dist[x] if dist[x] != -1 else default for x in range(N)]

    #最短路
    def shortest_path(self, u, v):
        """ u から v への最短路を求める (存在しない場合は None). """

        if u == v:
            return [u]

        from collections import deque

        prev = [-1] * self.order()
        prev[u] = u

        queue = deque([u])
        while queue:
            x = queue.popleft()
            for y in self.adjacent[x]:
                if prev[x] != -1:
                    continue

                prev[y] = x
                queue.append(y)

                if y != v:
                    continue

                path = [v]
                a = v
                while a != u:
                    a = prev[a]
                    path.append(a)
                return path[::-1]
        return None

    def edge_yielder(self):
        u = [0] * len(self.edge_alive); v = [0] * len(self.edge_alive)
        for x in range(self.order()):
            adj = self.adjacent[x]
            ids = self.edge_ids[x]

            for k in range(len(adj)):
                id = ids[k]
                u[id] = min(x, adj[k])
                v[id] = max(x, adj[k])

        for id in range(len(self.edge_alive)):
            if self.edge_alive[id]:
                yield (u[id], v[id])

    def edge_yielder_with_index(self):
        u = [0] * len(self.edge_alive); v = [0] * len(self.edge_alive)
        for x in range(self.order()):
            adj = self.adjacent[x]
            ids = self.edge_ids[x]

            for k in range(len(adj)):
                id = ids[k]
                u[id] = min(x, adj[k])
                v[id] = max(x, adj[k])

        for id in range(len(self.edge_alive)):
            if self.edge_alive[id]:
                yield (id, u[id], v[id])

def Lowlink(G: Graph, mode=0):
    """ G の ord, lowlink を求める.

    G: Graph

    output: (ord, lowlink)
    """

    from collections import deque

    N=G.vertex_count()
    ord=[-1]*N; low=[-1]*N
    flag=[0]*N
    adj=G.adjacent
    parent=[-1]*N

    #BFSパート
    for v in range(N):
        if flag[v]:
            continue

        k=0
        S=deque([v])
        T=[]

        while S:
            u=S.pop()
            if flag[u]:
                continue

            T.append(u)
            ord[u]=k
            k+=1
            flag[u]=1

            for w in G.neighborhood(u):
                if not flag[w]:
                    S.append(w)
                    parent[w]=u

        for u in T:
            low[u]=ord[u]

        for w in T[:0:-1]:
            for x in adj[w]:
                if w==v or x!=parent[w]:
                    low[w]=min(low[w],low[x],ord[x])

    if mode==0:
        return ord, low
    else:
        return ord, low, parent

#橋列挙
def Bridge(G: Graph):
    """ G にある橋の id を列挙する.

    G: Graph
    """

    ord, low = Lowlink(G)
    return [id for id, u, v in G.edge_yielder_with_index() if (ord[u] < low[v]) or (ord[v] < low[u])]

#==================================================
def solve():
    N = int(input())

    G = Graph(N + 1, 1)
    for j in range(1, N + 1):
        u, v = map(int, input().split())
        G.add_edge(u, v)

    bridges = set(Bridge(G))
    anti_bridges = [j for j in range(1, N + 1) if j not in bridges]
    return f'{len(anti_bridges)}\n{" ".join(map(str, anti_bridges))}'

#==================================================
import sys
input=sys.stdin.readline
write=sys.stdout.write

print(solve())

yukicoder

結果

テストケース

ソースコード