提出詳細

ソースコード

import sys

sys.setrecursionlimit(10 ** 6)
class unionfind:
    def __init__(self, n):
        self.parents = [-1 for i in range(n)]
    
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        
        if x == y:
            return
            
        if self.parents[x] > self.parents[y]:
            x, y = y, x
            
        self.parents[x] = -2
        self.parents[y] = x
    
    def connectivity(self):
        if len([i for i in range(26) if self.parents[i] == -2]) == 1:
            return True
        [print(self.parents[i]) for i in range(26)]
        return False

ans = []
for i in range(int(input())):
    n = int(input())
    w = [input() for i in range(n)]
    
    head = {chr(i):0 for i in range(ord('a'), ord('z') + 1)}
    tail = {chr(i):0 for i in range(ord('a'), ord('z') + 1)}
    for i in w:
        head[i[0]] += 1
        tail[i[-1]] += 1
    
    tmp = False
    for i in range(ord('a'), ord('z') + 1):
        if head[chr(i)] != tail[chr(i)]:
            tmp = True
            break
            
    if tmp:
        ans.append('NG')
        continue
    
    if n == 1:
        ans.append('OK')
        continue
    
    uf = unionfind(26)
    for i in w:
        if i[0] != i[-1]:
            uf.union(ord(i[0]) - ord('a'), ord(i[-1]) - ord('a'))
    ans.append('OK' if uf.connectivity() else 'NG')

for i, x in enumerate(ans):
    print('Case #' + str(i + 1) + ':')
    print(x)

提出情報

提出時間 2020-04-16 17:01:55
問題 K - ワードサークル
ユーザ名 konchan
状態 形式違反
正解率 N/A
提出出力結果

テストケース情報

# 状態 詳細情報
正解か誤答の場合のみ表示されます．