ABC139 E — League

1# -*- coding: utf-8 -*-2 3 4from collections import deque5from typing import List, Tuple6 7 8class TopologicalSorting:9    """10    See:11    https://atcoder.jp/contests/abc291/submissions/3924105512    """13 14    def __init__(self, vertex_count: int) -> None:15        self.vertex_count = vertex_count16        self.graph = [[] for _ in range(vertex_count)]17        self.indegrees = [0] * vertex_count18 19    def add_edge(self, frm: int, to: int) -> None:20        """21        Args:22            frm(from) -> to: Vertex number (0-indexed).23        """24        assert 0 <= frm < self.vertex_count25        assert 0 <= to < self.vertex_count26 27        self.graph[frm].append(to)28        self.indegrees[to] += 129 30    def sort(self) -> Tuple[bool, List[int]]:31        """32        Returns:33            is_DAG: Is it DAG (Directed Acyclic Graph) ?34            orders: Order of vertices (0-indexed).35        """36        que = deque([i for i in range(self.vertex_count) if self.indegrees[i] == 0])37        results = list()38        cost = [1] * self.vertex_count39 40        if len(que) == 0:41            return False, []42 43        while que:44            # 起点となる頂点が複数存在してもok45            # if len(que) >= 2:46            #     return False, []47 48            vertex = que.popleft()49            results.append(vertex)50 51            for to in self.graph[vertex]:52                self.indegrees[to] -= 153                # トポロジカルソートをしながらコストを更新54                cost[to] = max(cost[to], cost[vertex] + 1)55 56                if self.indegrees[to] == 0:57                    que.append(to)58 59        if len(results) == self.vertex_count:60            return True, cost61        else:62            return False, []63 64 65def main():66    import sys67    from collections import defaultdict68 69    input = sys.stdin.readline70 71    n = int(input())72    a = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(n)]73 74    # 試合を頂点、各選手が行う試合の順番を有向グラフと捉える75    # DAG + 最長経路問題76    # 選手と試合のidの対応づけ77    ids = defaultdict(int)78    id = 079 80    for i in range(n):81        for j in range(i + 1, n):82            ids[(i, j)] = id83            id += 184 85    def to_id(i, j):86        if i > j:87            i, j = j, i88 89        return ids[(i, j)]90 91    vertex_count = n * (n - 1) // 292    ts = TopologicalSorting(vertex_count)93 94    for i in range(n):95        # 選手番号から試合のidに変換96        for j in range(n - 1):97            a[i][j] = to_id(i, a[i][j])98 99        # 各選手に対して、指定された日程の順番に辺を張る100        for ui, vi in zip(a[i], a[i][1:]):101            ts.add_edge(vi, ui)102 103    is_DAG, dist = ts.sort()104 105    if is_DAG:106        print(max(dist))107    else:108        print(-1)109 110 111if __name__ == "__main__":112    main()113