Участник:Kozub/Play on Words

Материал из DISCOPAL
Перейти к: навигация, поиск

Ссылка на задачу на Spojcode: https://www.spoj.com/problems/WORDS1

alphabet_len = 26
f_char = ord('a')
 
T = int(input())
for _ in range(T):
 
    N = int(input())
 
    conn = list([])
 
    graph = [0, ]* alphabet_len
    for _ in range(N):
        t_str = input()
        s, e = ord(t_str[0]) - f_char, ord(t_str[-1]) - f_char
        graph[s] +=1
        graph[e] -=1
 
 
        s_id, e_id = -1, -1
        for i,st in enumerate(conn):
            if s in st:
                s_id = i
            if e in st:
                e_id = i
 
        if s_id == -1 and e_id == -1:
            conn.append({s,e})
        elif s_id == e_id:
            continue
        elif s_id == -1:
            conn[e_id].add(s)
        elif e_id == -1:
            conn[s_id].add(e)
        else:
            conn[s_id] |= conn[e_id]
            del conn[e_id]
 
 
    if len(conn) > 1:
        print('The door cannot be opened.')
        continue
 
    big_disb_flag = False
    nz_num = 0
    for i in range(alphabet_len):
        if graph[i] != 0:
            nz_num+=1
            if abs(graph[i]) > 1:
                big_disb_flag = True
                break
 
    if big_disb_flag or (nz_num > 2):
        print('The door cannot be opened.')
    else:
        print('Ordering is possible.')