質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

87.34%

DAGとTopological sortについて

受付中

回答 0

投稿

  • 評価
  • クリップ 0
  • VIEW 878

score 24

AtCoderの問題で、DAGの最長経路に帰着させる問題を解いたのですが、どうしてもTLEしてしまいます。
問題はこちら
言語はPyPy3を使用しています。

各試合(i,j)自体を頂点とし、頂点数|V|=N(N-1)/2、辺の数|E|=N(N-1)として、試合の順番を辺とした有向グラフと見做すようです。
O(N^2)で計算できていると自分では思っているのですが、Topological sort,最長経路計算の処理に無駄があるのでしょうか?
それとも別の場所の処理が時間を食っているのでしょうか?
まだまだ若輩者ですので、ご教授いただけると幸いです。

提出したコードを以下に記載しておきます。

import sys
input=sys.stdin.readline
def resolve():
    #%% import
    from itertools import product
    from collections import deque

    #%% input
    n=int(input())
    V=[(i,j) for i,j in product(range(n),range(n)) if i<j]
    N=len(V) # N=n*(n-1)//2

    #%% adjacency list
    outs={v:[] for v in V}
    indeg={v:0 for v in V}
    for i in range(n):
        edge=list(map(lambda x:int(x)-1,input().split()))
        for j in range(len(edge)-1): # 各iにつきn-1個の辺が与えられる
            v0 = (min(i,edge[j]),max(i,edge[j]))
            v1 = (min(i,edge[j+1]),max(i,edge[j+1]))
            outs[v0].append(v1)
            indeg[v1]+=1

    #%% topological sort
    Q=deque(v for v in V if indeg[v]==0)
    res=[]
    while(Q):
        v0=Q.popleft()
        res.append(v0)
        for v1 in outs[v0]:
            indeg[v1]-=1
            if indeg[v1]==0: Q.append(v1)

    #%% judge whether G is DAG
    if len(res)<N:
        print("-1")
        return

    #%% Longest Path Problem
    LP={v:1 for v in V}
    for v0 in res:
        for v1 in outs[v0]:
            LP[v1]=max(LP[v1],LP[v0]+1)
    print(max(LP.values()))

resolve()
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

まだ回答がついていません

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 87.34%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る

閲覧数の多いPythonの質問