結果
問題 | No.1553 Lovely City |
ユーザー |
![]() |
提出日時 | 2021-06-18 23:24:46 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 904 ms / 2,000 ms |
コード長 | 5,539 bytes |
コンパイル時間 | 278 ms |
コンパイル使用メモリ | 82,796 KB |
実行使用メモリ | 172,388 KB |
最終ジャッジ日時 | 2024-06-22 21:30:15 |
合計ジャッジ時間 | 20,909 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 26 |
ソースコード
import sysfrom collections import defaultdict, Counter, dequefrom itertools import permutations, combinations, product, combinations_with_replacement, groupby, accumulateimport operatorfrom math import sqrt, gcd, factorialfrom copy import deepcopy# from math import isqrt, prod,comb # python3.8用(notpypy)#from bisect import bisect_left,bisect_right#from functools import lru_cache,reduce#from heapq import heappush,heappop,heapify,heappushpop,heapreplace#from networkx.utils import UnionFind#from numba import njit, b1, i1, i4, i8, f8#from scipy.sparse import csr_matrix#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, NegativeCycleError# numba例 @njit(i1(i4[:], i8[:, :]),cache=True) 引数i4配列、i8 2次元配列,戻り値i1def input(): return sys.stdin.readline().rstrip()def divceil(n, k): return 1+(n-1)//k # n/kの切り上げを返すdef yn(hantei, yes='Yes', no='No'): print(yes if hantei else no)class scc_graph:def __init__(self, N):self.N = Nself.edges = []def csr(self):self.start = [0]*(self.N+1)self.elist = [0]*len(self.edges)for e in self.edges:self.start[e[0]+1] += 1for i in range(1, self.N+1):self.start[i] += self.start[i-1]counter = self.start[:]for e in self.edges:self.elist[counter[e[0]]] = e[1]counter[e[0]] += 1def add_edge(self, v, w):self.edges.append((v, w))def scc_ids(self):self.csr()N = self.Nnow_ord = group_num = 0visited = []low = [0]*Norder = [-1]*Nids = [0]*Nparent = [-1]*Nstack = []for i in range(N):if order[i] == -1:stack.append(i)stack.append(i)while stack:v = stack.pop()if order[v] == -1:low[v] = order[v] = now_ordnow_ord += 1visited.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] = velse:low[v] = min(low[v], order[to])else:if low[v] == order[v]:while True:u = visited.pop()order[u] = Nids[u] = group_numif u == v:breakgroup_num += 1if parent[v] != -1:low[parent[v]] = min(low[parent[v]], low[v])for i, x in enumerate(ids):ids[i] = group_num-1-xreturn group_num, idsdef scc(self):group_num, ids = self.scc_ids()groups = [[] for _ in range(group_num)]for i, x in enumerate(ids):groups[x].append(i)return groupsclass UnionFind():def __init__(self, n):self.n = nself.parents = [-1] * nself.group_num = ndef find(self, x):if self.parents[x] < 0:return xelse:self.parents[x] = self.find(self.parents[x])return self.parents[x]def union(self, x, y):x = self.find(x)y = self.find(y)if x == y:returnself.group_num -= 1if self.parents[x] > self.parents[y]:x, y = y, xself.parents[x] += self.parents[y]self.parents[y] = xdef size(self, x):return -self.parents[self.find(x)]def same(self, x, y):return self.find(x) == self.find(y)def members(self, x):root = self.find(x)return [i for i in range(self.n) if self.find(i) == root]def roots(self):return [i for i, x in enumerate(self.parents) if x < 0]def group_count(self):return self.group_numdef all_group_members(self):self.all_group_member = defaultdict(list)for i in range(self.n):self.all_group_member[self.find(i)].append(i)return self.all_group_memberdef __str__(self):return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())def main():n,m=map(int, input().split())uf=UnionFind(n)edges=[[] for i in range(n)]for i in range(m):a,b=map(lambda x: int(x)-1, input().split())uf.union(a,b)edges[a].append(b)ans=[]for mem in uf.all_group_members().values():sc=scc_graph(len(mem))memdic={mm:i for i,mm in enumerate(mem)}memdic2={i:mm for i,mm in enumerate(mem)}for mm in mem:for v in edges[mm]:sc.add_edge(memdic[mm],memdic[v])group=sc.scc()if all(len(gg)==1 for gg in group):for i in range(len(group)-1):ans.append([memdic2[group[i][0]]+1,memdic2[group[i+1][0]]+1])else:for i in range(len(mem)):ans.append([mem[i]+1,mem[i-1]+1])print(len(ans))for aa in ans:print(*aa)if __name__ == '__main__':main()