提出詳細

ソースコード

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
        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:03:11
問題 K - ワードサークル
ユーザ名 konchan
状態 正解
正解率 50/50
提出出力結果

テストケース情報

# 状態 詳細情報
テストケース 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 正解 詳細を見る