結果

問題 No.1553 Lovely City
ユーザー aaaaaaaaaa2230aaaaaaaaaa2230
提出日時 2021-06-19 15:53:27
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 834 ms / 2,000 ms
コード長 1,709 bytes
コンパイル時間 383 ms
コンパイル使用メモリ 82,424 KB
実行使用メモリ 137,428 KB
最終ジャッジ日時 2024-06-22 22:07:07
合計ジャッジ時間 19,721 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
55,304 KB
testcase_01 AC 41 ms
55,868 KB
testcase_02 AC 60 ms
80,196 KB
testcase_03 AC 46 ms
57,064 KB
testcase_04 AC 47 ms
57,540 KB
testcase_05 AC 56 ms
65,388 KB
testcase_06 AC 57 ms
66,472 KB
testcase_07 AC 51 ms
63,312 KB
testcase_08 AC 652 ms
109,876 KB
testcase_09 AC 656 ms
113,228 KB
testcase_10 AC 682 ms
123,700 KB
testcase_11 AC 567 ms
113,944 KB
testcase_12 AC 698 ms
125,884 KB
testcase_13 AC 578 ms
107,144 KB
testcase_14 AC 617 ms
117,428 KB
testcase_15 AC 601 ms
113,644 KB
testcase_16 AC 673 ms
114,252 KB
testcase_17 AC 576 ms
108,912 KB
testcase_18 AC 779 ms
135,640 KB
testcase_19 AC 812 ms
136,292 KB
testcase_20 AC 823 ms
136,360 KB
testcase_21 AC 819 ms
134,356 KB
testcase_22 AC 770 ms
130,624 KB
testcase_23 AC 807 ms
137,428 KB
testcase_24 AC 808 ms
134,980 KB
testcase_25 AC 834 ms
135,900 KB
testcase_26 AC 800 ms
128,568 KB
testcase_27 AC 817 ms
131,760 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque
class Unionfind:
     
    def __init__(self,n):
        self.uf = [-1]*n
 
    def find(self,x):
        if self.uf[x] < 0:
            return x
        else:
            self.uf[x] = self.find(self.uf[x])
            return self.uf[x]
 
    def same(self,x,y):
        return self.find(x) == self.find(y)
 
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.uf[x] > self.uf[y]:
            x,y = y,x
        self.uf[x] += self.uf[y]
        self.uf[y] = x
        return True
 
    def size(self,x):
        x = self.find(x)
        return -self.uf[x]

n,m = map(int,input().split())
uf = Unionfind(n+1)
e = [[] for i in range(n+1)]
deg = [0]*(n+1)
use = [0]*(n+1)
for _ in range(m):
    u,v = map(int,input().split())
    e[u].append(v)
    uf.union(u,v)
    use[u] = 1
    use[v] = 1
    deg[v] += 1
group = [[] for i in range(n+1)]
for i in range(n+1):
    if use[i]:
        group[uf.find(i)].append(i)
ans = []
for i in range(n+1):
    if group[i] == []:
        continue
    q = deque([])
    loop = 0
    for ind in group[i]:
        if deg[ind]:
            continue
        q.append(ind)
    order = []
    while q:
        now = q.pop()
        order.append(now)
        for nex in e[now]:
            deg[nex] -= 1
            if deg[nex] == 0:
                q.append(nex)
    if len(order) == len(group[i]):
        for x,y in zip(order,order[1:]):
            ans.append((x,y))
    else:
        for j in range(len(group[i])):
            x = group[i][j]
            y = group[i][(j+1)%len(group[i])]
            ans.append((x,y))
print(len(ans))
for x,y in ans:
    print(x,y)
0