結果

問題 No.1254 補強への架け橋
ユーザー 👑 KazunKazun
提出日時 2021-03-18 17:48:51
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 783 ms / 2,000 ms
コード長 5,781 bytes
コンパイル時間 327 ms
コンパイル使用メモリ 81,696 KB
実行使用メモリ 178,876 KB
最終ジャッジ日時 2024-11-16 21:07:33
合計ジャッジ時間 39,465 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 44 ms
54,400 KB
testcase_01 AC 47 ms
54,912 KB
testcase_02 AC 48 ms
55,040 KB
testcase_03 AC 47 ms
55,040 KB
testcase_04 AC 44 ms
55,296 KB
testcase_05 AC 45 ms
54,784 KB
testcase_06 AC 45 ms
54,784 KB
testcase_07 AC 47 ms
55,424 KB
testcase_08 AC 46 ms
55,168 KB
testcase_09 AC 47 ms
55,168 KB
testcase_10 AC 44 ms
55,116 KB
testcase_11 AC 44 ms
54,912 KB
testcase_12 AC 44 ms
54,784 KB
testcase_13 AC 44 ms
54,912 KB
testcase_14 AC 45 ms
55,424 KB
testcase_15 AC 45 ms
55,296 KB
testcase_16 AC 45 ms
55,168 KB
testcase_17 AC 46 ms
55,040 KB
testcase_18 AC 45 ms
54,912 KB
testcase_19 AC 44 ms
55,168 KB
testcase_20 AC 45 ms
55,040 KB
testcase_21 AC 44 ms
55,168 KB
testcase_22 AC 45 ms
55,168 KB
testcase_23 AC 47 ms
55,040 KB
testcase_24 AC 46 ms
55,552 KB
testcase_25 AC 45 ms
55,324 KB
testcase_26 AC 45 ms
55,424 KB
testcase_27 AC 46 ms
55,296 KB
testcase_28 AC 47 ms
55,552 KB
testcase_29 AC 46 ms
55,380 KB
testcase_30 AC 45 ms
55,296 KB
testcase_31 AC 49 ms
55,424 KB
testcase_32 AC 46 ms
55,168 KB
testcase_33 AC 47 ms
55,040 KB
testcase_34 AC 46 ms
55,532 KB
testcase_35 AC 46 ms
55,552 KB
testcase_36 AC 47 ms
55,552 KB
testcase_37 AC 47 ms
55,808 KB
testcase_38 AC 47 ms
55,040 KB
testcase_39 AC 47 ms
55,296 KB
testcase_40 AC 46 ms
55,680 KB
testcase_41 AC 48 ms
55,552 KB
testcase_42 AC 47 ms
54,784 KB
testcase_43 AC 69 ms
70,272 KB
testcase_44 AC 50 ms
56,832 KB
testcase_45 AC 50 ms
57,216 KB
testcase_46 AC 66 ms
68,608 KB
testcase_47 AC 54 ms
63,104 KB
testcase_48 AC 66 ms
67,584 KB
testcase_49 AC 48 ms
55,552 KB
testcase_50 AC 74 ms
72,448 KB
testcase_51 AC 69 ms
71,552 KB
testcase_52 AC 70 ms
72,192 KB
testcase_53 AC 64 ms
69,248 KB
testcase_54 AC 73 ms
72,576 KB
testcase_55 AC 68 ms
70,144 KB
testcase_56 AC 48 ms
55,680 KB
testcase_57 AC 62 ms
66,688 KB
testcase_58 AC 64 ms
67,712 KB
testcase_59 AC 48 ms
55,808 KB
testcase_60 AC 51 ms
56,960 KB
testcase_61 AC 70 ms
70,144 KB
testcase_62 AC 48 ms
56,064 KB
testcase_63 AC 190 ms
84,732 KB
testcase_64 AC 119 ms
78,336 KB
testcase_65 AC 173 ms
81,024 KB
testcase_66 AC 154 ms
80,240 KB
testcase_67 AC 111 ms
78,428 KB
testcase_68 AC 155 ms
79,876 KB
testcase_69 AC 169 ms
81,372 KB
testcase_70 AC 127 ms
78,936 KB
testcase_71 AC 115 ms
78,208 KB
testcase_72 AC 176 ms
82,176 KB
testcase_73 AC 131 ms
79,176 KB
testcase_74 AC 164 ms
81,472 KB
testcase_75 AC 151 ms
80,768 KB
testcase_76 AC 95 ms
77,592 KB
testcase_77 AC 143 ms
80,000 KB
testcase_78 AC 184 ms
83,456 KB
testcase_79 AC 182 ms
83,780 KB
testcase_80 AC 176 ms
82,596 KB
testcase_81 AC 185 ms
83,772 KB
testcase_82 AC 186 ms
82,256 KB
testcase_83 AC 783 ms
177,772 KB
testcase_84 AC 703 ms
162,608 KB
testcase_85 AC 500 ms
144,764 KB
testcase_86 AC 628 ms
151,128 KB
testcase_87 AC 684 ms
163,616 KB
testcase_88 AC 201 ms
87,872 KB
testcase_89 AC 726 ms
176,364 KB
testcase_90 AC 497 ms
139,492 KB
testcase_91 AC 427 ms
129,360 KB
testcase_92 AC 274 ms
100,584 KB
testcase_93 AC 614 ms
164,340 KB
testcase_94 AC 557 ms
145,020 KB
testcase_95 AC 547 ms
147,936 KB
testcase_96 AC 691 ms
167,736 KB
testcase_97 AC 370 ms
122,824 KB
testcase_98 AC 709 ms
163,128 KB
testcase_99 AC 466 ms
135,904 KB
testcase_100 AC 775 ms
178,208 KB
testcase_101 AC 253 ms
98,436 KB
testcase_102 AC 188 ms
86,028 KB
testcase_103 AC 273 ms
101,256 KB
testcase_104 AC 311 ms
110,568 KB
testcase_105 AC 601 ms
156,284 KB
testcase_106 AC 394 ms
124,408 KB
testcase_107 AC 745 ms
176,976 KB
testcase_108 AC 738 ms
173,960 KB
testcase_109 AC 615 ms
155,652 KB
testcase_110 AC 540 ms
147,308 KB
testcase_111 AC 568 ms
148,544 KB
testcase_112 AC 301 ms
107,892 KB
testcase_113 AC 525 ms
149,108 KB
testcase_114 AC 367 ms
118,076 KB
testcase_115 AC 214 ms
91,356 KB
testcase_116 AC 435 ms
127,140 KB
testcase_117 AC 303 ms
108,344 KB
testcase_118 AC 719 ms
173,784 KB
testcase_119 AC 470 ms
135,616 KB
testcase_120 AC 670 ms
166,324 KB
testcase_121 AC 268 ms
104,228 KB
testcase_122 AC 417 ms
126,600 KB
testcase_123 AC 42 ms
55,424 KB
testcase_124 AC 729 ms
178,512 KB
testcase_125 AC 733 ms
178,876 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)))
0