-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy patha.py
More file actions
93 lines (62 loc) · 2.37 KB
/
a.py
File metadata and controls
93 lines (62 loc) · 2.37 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
from __future__ import annotations
import itertools
from collections.abc import Iterable, Iterator
from typing import Self
class Edge:
vertices: tuple[int, int]
def __init__(self, vertices: Iterable[int]) -> None:
vertices_list = list(itertools.islice(vertices, 2))
self.vertices = vertices_list[0], vertices_list[1]
def __getitem__(self, index: int) -> int:
return self.vertices[index]
@classmethod
def read(cls) -> Self:
vertices_iter = map(lambda vertex_str: int(vertex_str) - 1, input().split())
return cls(vertices_iter)
@classmethod
def read_list(cls, count: int) -> Iterable[Self]:
for i in range(count):
yield cls.read()
class AdjacencyList:
vertices: list[int]
def __init__(self) -> None:
self.vertices = []
def __len__(self) -> int:
return len(self.vertices)
def __iter__(self) -> Iterator[int]:
yield from self.vertices
def as_list(self) -> Iterable[int]:
return map(lambda vertex: vertex + 1, self)
def add_vertex(self, vertex: int) -> None:
self.vertices.append(vertex)
def sort(self) -> None:
self.vertices.sort()
class Graph:
adjacency_lists: list[AdjacencyList]
def __init__(self, *, vertices_count: int = 0) -> None:
self.adjacency_lists = []
self.create_vertices(vertices_count)
def __iter__(self) -> Iterator[AdjacencyList]:
yield from self.adjacency_lists
def create_vertices(self, count: int) -> None:
self.adjacency_lists.extend(AdjacencyList() for _i in range(count))
def add_edge(self, edge: Edge) -> None:
adjacency_list = self.adjacency_lists[edge[0]]
adjacency_list.add_vertex(edge[1])
def sort(self) -> None:
for adjacency_list in self:
adjacency_list.sort()
@classmethod
def read(cls, *, vertices_count: int, edges_count: int) -> Self:
graph = cls(vertices_count=vertices_count)
for edge in Edge.read_list(edges_count):
graph.add_edge(edge)
graph.sort()
return graph
def main() -> None:
vertices_count, edges_count = map(int, input().split())
graph = Graph.read(vertices_count=vertices_count, edges_count=edges_count)
for adjacency_list in graph:
print(len(adjacency_list), *adjacency_list.as_list())
if __name__ == '__main__':
main()