結果

問題 No.1983 [Cherry 4th Tune C] 南の島のマーメイド
ユーザー hirayuu_ychirayuu_yc
提出日時 2023-11-21 14:30:50
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,899 ms / 4,000 ms
コード長 2,925 bytes
コンパイル時間 228 ms
コンパイル使用メモリ 82,348 KB
実行使用メモリ 216,488 KB
最終ジャッジ日時 2024-09-26 07:10:36
合計ジャッジ時間 44,215 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 43 ms
54,272 KB
testcase_01 AC 43 ms
54,016 KB
testcase_02 AC 43 ms
54,400 KB
testcase_03 AC 43 ms
54,784 KB
testcase_04 AC 46 ms
54,656 KB
testcase_05 AC 43 ms
54,272 KB
testcase_06 AC 43 ms
54,400 KB
testcase_07 AC 44 ms
54,656 KB
testcase_08 AC 208 ms
79,528 KB
testcase_09 AC 237 ms
80,860 KB
testcase_10 AC 253 ms
84,252 KB
testcase_11 AC 289 ms
84,848 KB
testcase_12 AC 270 ms
81,148 KB
testcase_13 AC 1,174 ms
131,060 KB
testcase_14 AC 1,303 ms
148,092 KB
testcase_15 AC 1,337 ms
147,780 KB
testcase_16 AC 745 ms
113,352 KB
testcase_17 AC 1,314 ms
156,012 KB
testcase_18 AC 1,153 ms
147,636 KB
testcase_19 AC 1,359 ms
178,360 KB
testcase_20 AC 1,179 ms
144,980 KB
testcase_21 AC 1,304 ms
156,644 KB
testcase_22 AC 1,415 ms
185,020 KB
testcase_23 AC 1,827 ms
196,636 KB
testcase_24 AC 1,878 ms
196,696 KB
testcase_25 AC 1,874 ms
196,568 KB
testcase_26 AC 1,874 ms
196,700 KB
testcase_27 AC 1,899 ms
197,212 KB
testcase_28 AC 1,862 ms
196,680 KB
testcase_29 AC 1,852 ms
197,576 KB
testcase_30 AC 1,803 ms
195,804 KB
testcase_31 AC 1,818 ms
196,208 KB
testcase_32 AC 1,780 ms
195,152 KB
testcase_33 AC 45 ms
54,272 KB
testcase_34 AC 746 ms
106,912 KB
testcase_35 AC 1,060 ms
203,580 KB
testcase_36 AC 1,056 ms
183,208 KB
testcase_37 AC 44 ms
54,272 KB
testcase_38 AC 593 ms
77,952 KB
testcase_39 AC 1,265 ms
212,804 KB
testcase_40 AC 1,257 ms
216,488 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class Graph():
    def __init__(self,size,directed=False):
        self.dir=directed
        self.size=size
        self.gr=[[] for i in range(size)]
        self.edges=[]
    
    def add_edge(self,u,v,status={}):
        self.gr[u].append(self.Edge(u,v,status))
        if not(self.dir):
            self.gr[v].append(self.Edge(v,u,status))
        self.edges.append(self.Edge(u,v,status))

    def node(self,v):
        return self.gr[v]
    
    class Edge():
        def __init__(self,st,to,status):
            self.st=st
            self.to=to
            self.status=status
        
        def __getitem__(self,val):
            return self.status[val]

from collections import deque
def bridge(gr):
    pre=[-1]*gr.size
    low=[-1]*gr.size
    ret=[]
    for i in range(gr.size):
        if pre[i]!=-1:
            continue
        vert=deque([[0,i,-1,-1]])
        cnt=0
        while len(vert)>0:
            step,now,bef,ed=vert[-1]
            if step==1:
                for j in gr.node(now):
                    if j.to!=bef:
                        low[now]=min(low[now],low[j.to])
                if ed!=-1 and pre[now]<=low[now]:
                    ret.append(gr.node(bef)[ed])
                vert.pop()
                continue
            if pre[now]!=-1:
                low[bef]=min(low[bef],low[now])
                vert.pop()
                continue
            pre[now]=cnt
            low[now]=cnt
            cnt+=1
            vert[-1][0]=1
            for j,k in enumerate(gr.node(now)):
                if k.to==bef:
                    continue
                if low[k.to]==-1:
                    vert.append([0,k.to,now,j])
                else:
                    low[now]=min(low[now],low[k.to])
    return ret

class UnionFind():
    def __init__(self,size):
        self.uf=[[-1,0,1] for i in range(size)]
        
    def unite(self,fir,sec):
        one=self.root(fir)
        two=self.root(sec)
        if one!=two:
            if self.uf[one][1]>self.uf[two][1]:
                one,two=two,one
            self.uf[one][0]=two
            self.uf[two][2]+=self.uf[one][2]
            if self.uf[one][1]==self.uf[two][1]:
                self.uf[two][1]+=1
    
    def same(self,fir,sec):
        return self.root(fir)==self.root(sec)
    
    def root(self,node):
        pos=node
        change=[]
        while self.uf[pos][0]!=-1:
            change.append(pos)
            pos=self.uf[pos][0]
        for i in change:
            self.uf[i][0]=pos
        return pos
    
    def size(self,node):
        return self.uf[self.root(node)][2]

N,M,Q=map(int,input().split())
namori=Graph(N)
for i in range(M):
    u,v=map(int,input().split())
    namori.add_edge(u-1,v-1)
union=UnionFind(N)
for i in bridge(namori):
    union.unite(i.st,i.to)
for i in range(Q):
    x,y=map(int,input().split())
    if union.same(x-1,y-1):
        print("Yes")
    else:
        print("No")
0