結果

問題 No.1553 Lovely City
ユーザー DrDrpilotDrDrpilot
提出日時 2022-06-20 18:06:51
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
WA  
実行時間 -
コード長 2,253 bytes
コンパイル時間 215 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 102,568 KB
最終ジャッジ日時 2024-10-13 06:06:06
合計ジャッジ時間 38,253 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 TLE -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

class StrongConnection:
  def __init__(self, N):
    self.N = N + 1
    self.edges = []
  def csr(self):
    start = [0] * (self.N + 1)
    elist = [0] * len(self.edges)
    for e in self.edges:
      start[e[0] + 1] += 1
    for i in range(1, self.N + 1):
      start[i] += start[i - 1]
    counter = start[:]
    for e in self.edges:
      elist[counter[e[0]]] = e[1]
      counter[e[0]] += 1
    self.start = start
    self.elist = elist
  def add_edge(self, v, w): self.edges.append((v, w))
  def scc_ids(self):
    self.csr()
    N = self.N
    now_ord = group_num = 0
    visited = []
    low = [0] * N
    order = [-1] * N
    ids = [0] * N
    parent = [-1] * N
    stack = []
    for i in range(N):
      if order[i] == -1:
        stack.append(~i)
        stack.append(i)
        while stack:
          v = stack.pop()
          if v >= 0:
            if order[v] == -1:
              low[v] = order[v] = now_ord
              now_ord += 1
              visited.append(v)
              for i in range(self.start[v], self.start[v + 1]):
                to = self.elist[i]
                if order[to] == -1:
                  stack.append(~to)
                  stack.append(to)
                  parent[to] = v
                else:
                  low[v] = min(low[v], order[to])
          else:
            v = ~v
            if low[v] == order[v]:
              while True:
                u = visited.pop()
                order[u] = N
                ids[u] = group_num
                if u == v:
                  break
              group_num += 1
            if parent[v] != -1:
              low[parent[v]] = min(low[parent[v]], low[v])
    for i, x in enumerate(ids):
      ids[i] = group_num - 1 - x
    return group_num, ids
  def groups(self):
    group_num, ids = self.scc_ids()
    groups = [[] for _ in range(group_num)]
    for i, x in enumerate(ids):
      groups[x].append(i)
    return groups
n,m=map(int,input().split())
scc = StrongConnection(n)

e=[[] for _ in range(n+1)]
for _ in range(m):
    a,b=map(int,input().split())
    scc.add_edge(a,b)
    e[b].append(a)
g = scc.groups()
g=g[::-1][1:]
n=len(g)
print(n-1)
for i in range(n-1):
    l=g[i];t=g[i+1]
    print(l[-1],t[0])
0