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

• 問題: No.1254 補強への架け橋
• ユーザー: 👑 Kazun
• 提出日時: 2021-03-18 17:48:51
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 632 ms / 2,000 ms
• コード長: 5,781 bytes
• コンパイル時間: 185 ms
• コンパイル使用メモリ: 82,048 KB
• 実行使用メモリ: 178,992 KB
• 最終ジャッジ日時: 2024-04-28 07:34:45
• 合計ジャッジ時間: 33,831 ms
• ジャッジサーバーID （参考情報）: judge5 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	42 ms; 54,528 KB
testcase_01	AC	41 ms; 54,912 KB
testcase_02	AC	43 ms; 55,040 KB
testcase_03	AC	41 ms; 54,656 KB
testcase_04	AC	42 ms; 55,040 KB
testcase_05	AC	43 ms; 54,912 KB
testcase_06	AC	45 ms; 54,912 KB
testcase_07	AC	43 ms; 54,912 KB
testcase_08	AC	41 ms; 55,040 KB
testcase_09	AC	43 ms; 54,784 KB
testcase_10	AC	44 ms; 54,784 KB
testcase_11	AC	43 ms; 55,040 KB
testcase_12	AC	43 ms; 54,912 KB
testcase_13	AC	43 ms; 55,168 KB
testcase_14	AC	43 ms; 55,296 KB
testcase_15	AC	44 ms; 55,168 KB
testcase_16	AC	43 ms; 54,912 KB
testcase_17	AC	42 ms; 54,912 KB
testcase_18	AC	41 ms; 55,296 KB
testcase_19	AC	43 ms; 54,656 KB
testcase_20	AC	43 ms; 55,552 KB
testcase_21	AC	44 ms; 55,040 KB
testcase_22	AC	43 ms; 55,424 KB
testcase_23	AC	42 ms; 55,296 KB
testcase_24	AC	43 ms; 55,424 KB
testcase_25	AC	43 ms; 54,912 KB
testcase_26	AC	43 ms; 55,552 KB
testcase_27	AC	43 ms; 55,168 KB
testcase_28	AC	43 ms; 55,168 KB
testcase_29	AC	43 ms; 55,424 KB
testcase_30	AC	41 ms; 54,912 KB
testcase_31	AC	45 ms; 55,680 KB
testcase_32	AC	43 ms; 55,296 KB
testcase_33	AC	43 ms; 55,424 KB
testcase_34	AC	42 ms; 55,424 KB
testcase_35	AC	42 ms; 55,296 KB
testcase_36	AC	41 ms; 55,168 KB
testcase_37	AC	47 ms; 55,492 KB
testcase_38	AC	51 ms; 55,680 KB
testcase_39	AC	49 ms; 55,040 KB
testcase_40	AC	43 ms; 55,040 KB
testcase_41	AC	46 ms; 54,912 KB
testcase_42	AC	44 ms; 55,040 KB
testcase_43	AC	69 ms; 70,400 KB
testcase_44	AC	46 ms; 57,088 KB
testcase_45	AC	48 ms; 56,704 KB
testcase_46	AC	63 ms; 68,736 KB
testcase_47	AC	52 ms; 62,848 KB
testcase_48	AC	61 ms; 67,200 KB
testcase_49	AC	43 ms; 55,168 KB
testcase_50	AC	71 ms; 72,960 KB
testcase_51	AC	71 ms; 71,552 KB
testcase_52	AC	75 ms; 71,936 KB
testcase_53	AC	67 ms; 69,376 KB
testcase_54	AC	72 ms; 72,704 KB
testcase_55	AC	66 ms; 70,400 KB
testcase_56	AC	45 ms; 55,808 KB
testcase_57	AC	64 ms; 66,816 KB
testcase_58	AC	65 ms; 67,712 KB
testcase_59	AC	43 ms; 55,680 KB
testcase_60	AC	47 ms; 56,704 KB
testcase_61	AC	66 ms; 70,400 KB
testcase_62	AC	42 ms; 55,808 KB
testcase_63	AC	169 ms; 84,992 KB
testcase_64	AC	113 ms; 78,336 KB
testcase_65	AC	148 ms; 80,768 KB
testcase_66	AC	139 ms; 80,796 KB
testcase_67	AC	107 ms; 78,336 KB
testcase_68	AC	144 ms; 80,000 KB
testcase_69	AC	162 ms; 81,752 KB
testcase_70	AC	119 ms; 79,104 KB
testcase_71	AC	118 ms; 78,208 KB
testcase_72	AC	163 ms; 82,176 KB
testcase_73	AC	123 ms; 78,848 KB
testcase_74	AC	147 ms; 81,852 KB
testcase_75	AC	143 ms; 80,640 KB
testcase_76	AC	101 ms; 77,440 KB
testcase_77	AC	137 ms; 80,256 KB
testcase_78	AC	192 ms; 83,456 KB
testcase_79	AC	187 ms; 84,096 KB
testcase_80	AC	189 ms; 83,080 KB
testcase_81	AC	163 ms; 83,968 KB
testcase_82	AC	166 ms; 82,776 KB
testcase_83	AC	609 ms; 177,636 KB
testcase_84	AC	580 ms; 162,360 KB
testcase_85	AC	403 ms; 144,640 KB
testcase_86	AC	525 ms; 150,736 KB
testcase_87	AC	575 ms; 163,604 KB
testcase_88	AC	185 ms; 87,856 KB
testcase_89	AC	622 ms; 176,504 KB
testcase_90	AC	416 ms; 140,004 KB
testcase_91	AC	356 ms; 129,044 KB
testcase_92	AC	237 ms; 100,580 KB
testcase_93	AC	495 ms; 164,212 KB
testcase_94	AC	435 ms; 144,892 KB
testcase_95	AC	455 ms; 148,324 KB
testcase_96	AC	588 ms; 167,784 KB
testcase_97	AC	331 ms; 122,956 KB
testcase_98	AC	572 ms; 163,656 KB
testcase_99	AC	383 ms; 135,776 KB
testcase_100	AC	627 ms; 177,824 KB
testcase_101	AC	229 ms; 98,364 KB
testcase_102	AC	174 ms; 86,220 KB
testcase_103	AC	229 ms; 101,300 KB
testcase_104	AC	259 ms; 110,688 KB
testcase_105	AC	495 ms; 156,336 KB
testcase_106	AC	319 ms; 124,152 KB
testcase_107	AC	632 ms; 177,368 KB
testcase_108	AC	594 ms; 173,804 KB
testcase_109	AC	482 ms; 155,656 KB
testcase_110	AC	451 ms; 146,928 KB
testcase_111	AC	473 ms; 148,920 KB
testcase_112	AC	271 ms; 107,760 KB
testcase_113	AC	437 ms; 149,184 KB
testcase_114	AC	320 ms; 117,564 KB
testcase_115	AC	190 ms; 91,320 KB
testcase_116	AC	356 ms; 127,532 KB
testcase_117	AC	274 ms; 108,476 KB
testcase_118	AC	584 ms; 174,160 KB
testcase_119	AC	378 ms; 135,488 KB
testcase_120	AC	549 ms; 166,064 KB
testcase_121	AC	242 ms; 103,852 KB
testcase_122	AC	370 ms; 126,812 KB
testcase_123	AC	43 ms; 55,296 KB
testcase_124	AC	615 ms; 178,384 KB
testcase_125	AC	601 ms; 178,992 KB

ソースコード

class Graph:
    #入力定義
    def __init__(self,vertex=[]):
        self.vertex=set(vertex)

        self.edge_number=0
        self.adjacent={v:set() for v in vertex}

    #頂点の追加
    def add_vertex(self,*adder):
        for v in adder:
            if not self.vertex_exist(v):
                self.adjacent[v]=set()
                self.vertex.add(v)

    #辺の追加
    def add_edge(self,u,v):
        self.add_vertex(u)
        self.add_vertex(v)

        if not self.edge_exist(u,v):
            self.adjacent[u].add(v)
            self.adjacent[v].add(u)
            self.edge_number+=1

    #辺を除く
    def remove_edge(self,u,v):
        self.add_vertex(u)
        self.add_vertex(v)

        if self.edge_exist(u,v):
            self.adjacent[u].discard(v)
            self.adjacent[v].discard(u)
            self.edge_number-=1

    #頂点を除く
    def remove_vertex(self,*vertexes):
        for v in vertexes:
            if self.vertex_exist(v):
                U=self.neighbohood(v)
                for u in U:
                    self.edge_number-=1
                    self.adjacent[u].discard(v)

                del self.adjacent[v]
                self.vertex.discard(v)

    #Walkの追加
    def add_walk(self,*walk):
        n=len(walk)
        for i in range(n-1):
            self.add_edge(walk[i],walk[i+1])

    #Cycleの追加
    def add_cycle(self,*cycle):
        self.add_walk(*cycle)
        self.add_edge(cycle[-1],cycle[0])

    #頂点の交換
    def __vertex_swap(self,p,q):
        self.vertex.sort()

    #グラフに頂点が存在するか否か
    def vertex_exist(self,v):
        return v in self.vertex

    #グラフに辺が存在するか否か
    def edge_exist(self,u,v):
        if not(self.vertex_exist(u) and self.vertex_exist(v)):
            return False
        return v in self.adjacent[u]

    #近傍
    def neighbohood(self,v):
        if not self.vertex_exist(v):
            return []
        return list(self.adjacent[v])

    #次数
    def degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent[v])

    #頂点数
    def vertex_count(self):
        return len(self.vertex)

    #辺数
    def edge_count(self):
        return self.edge_number

    #頂点vを含む連結成分
    def connected_component(self,v):
        if v not in self.adjacent:
            return []

        from collections import deque
        T={u:0 for u in self.vertex}
        T[v]=1
        Q=deque([v])
        while Q:
            u=Q.popleft()
            for w in self.adjacent[u]:
                if not T[w]:
                    T[w]=1
                    Q.append(w)
        return [x for x in self.adjacent if T[x]]

    #距離
    def distance(self,u,v):
        from collections import deque
        inf=float("inf")
        T={v:inf  for v in self.vertex}

        if u==v:
            return 0
        Q=deque([u])
        T[u]=0
        while Q:
            w=Q.popleft()
            for x in self.adjacent[w]:
                if T[x]==inf:
                    T[x]=T[w]+1
                    Q.append(x)
                    if x==v:
                        return T[x]
        return inf

    #ある1点からの距離
    def distance_all(self,u):
        from collections import deque
        inf=float("inf")
        T={v:inf  for v in self.vertex}

        Q=deque([u])
        T[u]=0
        while Q:
            w=Q.popleft()
            for x in self.adjacent[w]:
                if T[x]==inf:
                    T[x]=T[w]+1
                    Q.append(x)
        return T

    #最短路
    def shortest_path(self,u,v):
        from collections import deque
        inf=float("inf")
        T={v:None for v in self.vertex}

        if u==v:
            return [u]

        Q=deque([u])
        T[u]=u
        while Q:
            w=Q.popleft()
            for x in self.adjacent[w]:
                if not T[x]:
                    T[x]=w
                    Q.append(x)
                    if x==v:
                        P=[v]
                        a=v
                        while a!=u:
                            a=T[a]
                            P.append(a)
                        return P[::-1]
        return None

    #何かしらの頂点を選ぶ.
    def poping_vertex(self):
        v=self.vertex.pop()
        self.vertex.add(v)
        return v

def Bridge(G):
    from collections import deque

    B=[]
    ord={v:-1 for v in G.vertex}
    flag={v:0 for v in G.vertex}
    nei=G.adjacent

    #BFSパート
    for v in G.vertex:
        if flag[v]:
            continue

        k=0
        parent={}
        S=deque([v])
        T=[]
        X=[]

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

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

            if u!=v:
                X.append((parent[u],u))

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

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

        for u,w in X:
            if ord[u]<low[w]:
                B.append((u,w))
        return B
#================================================
import sys
input=sys.stdin.readline
write=sys.stdout.write

N=int(input())
G=Graph(range(1,N+1))
E={}

for i in range(1,N+1):
    a,b=map(int,input().split())

    if a>b:
        a,b=b,a

    G.add_edge(a,b)
    E[(a,b)]=i

B=set([(min(*p),max(*p)) for p in Bridge(G)])
T=[E[p] for p in E if p not in B]

print(len(T))
write(" ".join(map(str,T)))