結果

問題 No.1553 Lovely City
ユーザー Kiri8128Kiri8128
提出日時 2021-06-18 22:50:48
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 991 ms / 2,000 ms
コード長 4,080 bytes
コンパイル時間 316 ms
コンパイル使用メモリ 87,200 KB
実行使用メモリ 210,708 KB
最終ジャッジ日時 2023-09-04 23:58:11
合計ジャッジ時間 23,505 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 71 ms
70,764 KB
testcase_01 AC 72 ms
71,156 KB
testcase_02 AC 444 ms
167,068 KB
testcase_03 AC 84 ms
70,936 KB
testcase_04 AC 80 ms
71,056 KB
testcase_05 AC 90 ms
76,180 KB
testcase_06 AC 82 ms
75,432 KB
testcase_07 AC 80 ms
75,108 KB
testcase_08 AC 667 ms
157,388 KB
testcase_09 AC 694 ms
163,280 KB
testcase_10 AC 747 ms
173,552 KB
testcase_11 AC 576 ms
147,260 KB
testcase_12 AC 813 ms
182,064 KB
testcase_13 AC 625 ms
146,028 KB
testcase_14 AC 649 ms
159,292 KB
testcase_15 AC 632 ms
158,416 KB
testcase_16 AC 717 ms
168,292 KB
testcase_17 AC 590 ms
153,212 KB
testcase_18 AC 969 ms
207,572 KB
testcase_19 AC 991 ms
209,480 KB
testcase_20 AC 920 ms
208,700 KB
testcase_21 AC 898 ms
210,708 KB
testcase_22 AC 918 ms
207,300 KB
testcase_23 AC 933 ms
207,196 KB
testcase_24 AC 911 ms
207,796 KB
testcase_25 AC 937 ms
207,940 KB
testcase_26 AC 948 ms
210,128 KB
testcase_27 AC 908 ms
207,868 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.PA = [-1] * n
    def root(self, a):
        L = []
        while self.PA[a] >= 0:
            L.append(a)
            a = self.PA[a]
        for l in L:
            self.PA[l] = a
        return a
    def unite(self, a, b):
        ra, rb = self.root(a), self.root(b)
        if ra != rb:
            if self.PA[rb] >= self.PA[ra]:
                self.PA[ra] += self.PA[rb]
                self.PA[rb] = ra
            else:
                self.PA[rb] += self.PA[ra]
                self.PA[ra] = rb
    def size(self, a):
        return -self.PA[self.root(a)]
    def groups(self):
        G = [[] for _ in range(self.n)]
        for i in range(self.n):
            G[self.root(i)].append(i)
        return [g for g in G if g]
    def groups_index(self):
        G = [[] for _ in range(self.n)]
        for i in range(self.n):
            G[self.root(i)].append(i)
        cnt = 0
        GG = []
        I = [-1] * self.n
        for i in range(self.n):
            if G[i]:
                GG.append(G[i])
                I[i] = cnt
                cnt += 1
        return GG, I
    def group_size(self):
        G = [[] for _ in range(self.n)]
        for i in range(self.n):
            G[self.root(i)].append(i)
        return [len(g) for g in G if g]

def scc(E):
    n = len(E)
    iE = [[] for _ in range(n)]
    for i, e in enumerate(E):
        for v in e:
            iE[v].append(i)
    T = []
    done = [0] * n # 0 -> 1 -> 2
    ct = 0
    for i0 in range(n):
        if done[i0]: continue
        Q = [~i0, i0]
        while Q:
            i = Q.pop()
            if i < 0:
                if done[~i] == 2: continue
                done[~i] = 2
                T.append(~i)
                ct += 1
                continue
            if i >= 0:
                if done[i]: continue
                done[i] = 1
            for j in E[i]:
                if done[j]: continue
                Q.append(~j)
                Q.append(j)
    
    done = [0] * n
    SCC = []
    ### ID が必要なとき
    I = [0] * n
    ###
    for i0 in T[::-1]:
        if done[i0]: continue
        L = []
        Q = [~i0, i0]
        while Q:
            i = Q.pop()
            if i < 0:
                if done[~i] == 2: continue
                done[~i] = 2
                L.append(~i)
                ###
                I[~i] = len(SCC)
                ###
                continue
            if i >= 0:
                if done[i]: continue
                done[i] = 1
            for j in iE[i]:
                if done[j]: continue
                Q.append(~j)
                Q.append(j)
        SCC.append(L)
    return SCC, I
    
    ### ↓ Edge が必要なとき （上の return を消す）
    nE = [set() for _ in range(len(SCC))]
    iE = [set() for _ in range(len(SCC))]
    for i, e in enumerate(E):
        for j in e:
            if I[i] == I[j]: continue
            # print("i, j, I[i], I[j] =", i, j, I[i], I[j])
            nE[I[i]].add(I[j])
            iE[I[j]].add(I[i])
    nE = [list(e) for e in nE]
    iE = [list(e) for e in iE]
    return SCC, I, nE, iE

import sys
input = lambda: sys.stdin.readline().rstrip()
N, M = map(int, input().split())
X = []
for _ in range(M):
    a, b = map(int, input().split())
    X.append((a-1, b-1))

uf = UnionFind(N)
for a, b in X:
    uf.unite(a, b)

# G = uf.groups()
# print(G)
GG, I = uf.groups_index()
K = len(GG)
D = [{v: f for f, v in enumerate(GG[i])} for i in range(K)]
XX = [[] for _ in range(K)]
for a, b in X:
    g = I[uf.root(a)]
    XX[g].append((D[g][a], D[g][b]))
ANS = []
for i in range(K):
    gg = GG[i]
    si = len(gg)
    E = [[] for _ in range(si)]
    for a, b in XX[i]:
        E[a].append(b)
    SCC, II = scc(E)
    
    if len(SCC) < si:
        for j in range(si):
            ANS.append(str(gg[j-1] + 1) + " " + str(gg[j] + 1))
    else:
        for j in range(si - 1):
            ANS.append(str(gg[SCC[j][0]] + 1) + " " + str(gg[SCC[j+1][0]] + 1))
    
print(len(ANS))
print("\n".join(ANS))
0