結果

問題 No.3321 岩井星人グラフ-1
コンテスト
ユーザー kidodesu
提出日時 2025-11-01 03:03:44
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,122 bytes
コンパイル時間 313 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 228,764 KB
最終ジャッジ日時 2025-11-01 03:04:10
合計ジャッジ時間 25,872 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 76 WA * 9 RE * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    n, m = map(int, input().split())
    if n - 1 != m:
        return "No"
    node = [[] for _ in range(n)]
    V = [0] * n
    C = set()
    for _ in range(m):
        u, v = [int(x)-1 for x in input().split()]
        node[u].append(v)
        node[v].append(u)
        V[u] += 1
        V[v] += 1
        C.add((u, v))
        C.add((v, u))
    v_ = max(V)
    if v_ != 3:
        return "No"
    V_ = V[:]
    L = [0] * 4
    for v in V:
        L[v] += 1
    line = []
    edge = []
    S = [i for i in range(n) if V_[i] <= 1]
    E = [1] * n
    while S:
        now = S.pop()
        if not V_[now]:
            line.append(E[now])
            continue
        for nxt in node[now]:
            if V_[nxt] == 0:
                continue
            elif V_[nxt] == 3:
                V_[now] -= 1
                edge.append(E[now])
            else:
                V_[now] -= 1
                V_[nxt] -= 1
                E[nxt] += E[now]
                if V_[nxt] == 1:
                    S.append(nxt)
    line.sort()
    edge.sort()
    f = 0
    I = []
    for i in range(n):
        v = V_[i]
        if v == 2:
            I.append(i)
            f += 1
    if f > 2:
        return "No"
    elif f == 2:
        print(I)
        if not line and L[1] == L[3] + 2 and not (I[0], I[1]) in C and edge and edge[0] == edge[-1]:
            return "Yes"
        else:
            return "No"
    elif f == 1:
        if len(line) == 1 and edge and line[0] == edge[0] == edge[-1]:
            return "Yes"
        elif len(line) == 1 and edge and line[0] == edge[0] * 2 + 1 == edge[-1] * 2 + 1:
            return "Yes"
        elif not line and edge and edge[-1]-1 == max(edge[:-1]) == min(edge[:-1]):
            return "Yes"
        else:
            return "No"
    
    if len(line) > 2:
        return "No"
    elif len(line) == 2:
        if line[0] == line[1] and line[0] % 2:
            t = line[0] // 2
            edge_ = edge[:] + [t, t, t, t]
            if L[1] == L[3] + 2 and min(edge_) == max(edge_):
                return "Yes"
            else:
                return "No"
        elif line[0] * 2 + 1 == line[1]:
            edge_ = edge[:] + [t, t, t]
            if L[0] and L[1] == L[3] and min(edge_) == max(edge_):
                return "Yes"
            elif L[1] - 2 == L[3] and min(edge_) == max(edge_):
                return "Yes"
            else:
                return "No"
        else:
            return "No"
    elif line:
        if not edge:
            return "No"
        elif edge[-1] - 1 == line[0] == edge[-2] == edge[0]:
            return "Yes"
        else:
            edge[0] += line[0]
            if not L[0]:
                L[1] -= 2
            if L[1] == L[3] and min(edge) == max(edge):
                return "Yes"
            else:
                return "No"
    else:
        if L[1] - 2 != L[3] or len(edge) <= 2:
            return "No"
        else:
            edge[-1] -= 1
            edge[-2] -= 1
            if min(edge) == max(edge):
                return "Yes"
            else:
                return "No"

print(main())
0