結果

問題 No.1553 Lovely City
ユーザー Kiri8128Kiri8128
提出日時 2021-06-18 22:49:06
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 4,057 bytes
コンパイル時間 323 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 206,216 KB
最終ジャッジ日時 2024-06-22 21:09:21
合計ジャッジ時間 19,312 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 36 ms
52,864 KB
testcase_01 AC 37 ms
53,376 KB
testcase_02 AC 364 ms
165,740 KB
testcase_03 RE -
testcase_04 RE -
testcase_05 AC 57 ms
66,048 KB
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 AC 629 ms
174,084 KB
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 AC 507 ms
151,904 KB
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
権限があれば一括ダウンロードができます

ソースコード

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((gg[j-1], gg[j]))
    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