結果
問題 | No.1553 Lovely City |
ユーザー |
![]() |
提出日時 | 2021-06-19 18:31:09 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,055 ms / 2,000 ms |
コード長 | 3,396 bytes |
コンパイル時間 | 445 ms |
コンパイル使用メモリ | 82,404 KB |
実行使用メモリ | 175,448 KB |
最終ジャッジ日時 | 2024-06-22 22:15:05 |
合計ジャッジ時間 | 23,250 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 26 |
ソースコード
from collections import defaultdictfrom collections import dequeclass UnionFind(object):def __init__(self, n=1):self.par = [i for i in range(n)]self.rank = [0 for _ in range(n)]self.size = [1 for _ in range(n)]def find(self, x):"""x が属するグループを探索して親を出す。"""if self.par[x] == x:return xelse:self.par[x] = self.find(self.par[x])return self.par[x]def union(self, x, y):"""x と y のグループを結合"""x = self.find(x)y = self.find(y)if x != y:if self.rank[x] < self.rank[y]:x, y = y, xif self.rank[x] == self.rank[y]:self.rank[x] += 1self.par[y] = xself.size[x] += self.size[y]def is_same(self, x, y):"""x と y が同じグループか否か"""return self.find(x) == self.find(y)def get_size(self, x):"""x が属するグループの要素数"""x = self.find(x)return self.size[x]def topological(graph, deg):start = []for i in range(len(deg)):if deg[i] == 0:start.append(i)topo = []while start:v = start.pop()topo.append(v)for u in graph[v]:deg[u] -= 1if deg[u] == 0:start.append(u)return topodef main():N,M = map(int,input().split())Q = []S = set([])for i in range(M):U,V = map(int,input().split())Q.append((U,V))S.add(U)S.add(V)L = list(S)n = len(S) #出てくる頂点の種類L.sort()dic = {} #元の番号→座圧後の番号revdic = {} #座圧後の番号→元の番号for i in range(n):dic[L[i]] = irevdic[i] = L[i]G = [[] for _ in range(n)]deg = [0]*nuf = UnionFind(n)for u,v in Q:uz = dic[u]vz = dic[v]G[uz].append(vz)deg[vz] += 1uf.union(uz,vz)#print(G)unidic = defaultdict(list)for i in range(n):par = uf.find(i)unidic[par].append(i)#連結成分ごとans = []for unit in unidic.values():start = deque([])for x in unit:if deg[x] == 0:start.append(x)topo = []while start:v = start.pop()topo.append(v)for u in G[v]:deg[u] -= 1if deg[u] == 0:start.append(u)#print("U",unit)#print("Topo",topo)if len(topo) == len(unit): #トポロジカルソート可能for i in range(len(topo)-1):s = topo[i]; t = topo[i+1]sori = revdic[s]; tori = revdic[t]ans.append([sori,tori])else:if len(unit) == 1:continueelse:for i in range(len(unit)):s = unit[i-1]; t = unit[i] #i==0の時に最後を持ってくるsori = revdic[s]; tori = revdic[t]ans.append([sori,tori])print(len(ans))for ret in ans:print(*ret)if __name__ == '__main__':main()