結果

問題 No.1553 Lovely City
ユーザー Kiri8128Kiri8128
提出日時 2021-06-18 22:50:48
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 928 ms / 2,000 ms
コード長 4,080 bytes
コンパイル時間 185 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 206,880 KB
最終ジャッジ日時 2024-06-22 21:11:35
合計ジャッジ時間 20,702 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
53,120 KB
testcase_01 AC 40 ms
52,992 KB
testcase_02 AC 392 ms
165,992 KB
testcase_03 AC 48 ms
56,832 KB
testcase_04 AC 49 ms
56,960 KB
testcase_05 AC 59 ms
66,176 KB
testcase_06 AC 53 ms
62,976 KB
testcase_07 AC 54 ms
60,928 KB
testcase_08 AC 593 ms
154,840 KB
testcase_09 AC 619 ms
160,896 KB
testcase_10 AC 666 ms
173,964 KB
testcase_11 AC 549 ms
145,080 KB
testcase_12 AC 776 ms
178,904 KB
testcase_13 AC 562 ms
147,636 KB
testcase_14 AC 587 ms
155,312 KB
testcase_15 AC 569 ms
153,676 KB
testcase_16 AC 648 ms
164,988 KB
testcase_17 AC 538 ms
152,032 KB
testcase_18 AC 928 ms
205,364 KB
testcase_19 AC 864 ms
206,216 KB
testcase_20 AC 851 ms
206,880 KB
testcase_21 AC 835 ms
205,332 KB
testcase_22 AC 873 ms
203,580 KB
testcase_23 AC 906 ms
206,352 KB
testcase_24 AC 875 ms
204,024 KB
testcase_25 AC 839 ms
206,048 KB
testcase_26 AC 849 ms
205,456 KB
testcase_27 AC 817 ms
203,664 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