Problem:


Problem Statement

We found a dictionary of the Ancient Civilization Mayo (ACM) during excavation of the ruins.
After analysis of the dictionary, we revealed they used a language that had not more than 26 letters.
So one of us mapped each letter to a different English alphabet and typed all the words in the dictionary into a computer.

How the words are ordered in the dictionary, especially whether they are ordered lexicographically, is an interesting topic to many people.
As a good programmer, you are requested to write a program to judge whether we can consider the words to be sorted in a lexicographical order.

Note:
In a lexicographical order, a word always precedes other words it is a prefix of.
For example, ab 
precedes abc, 
abde, and so on.

Input

The input consists of multiple datasets. Each dataset is formatted as follows:

n
string_1
...
string_n

Each dataset consists of n+1 lines.
The first line of each dataset contains an integer that indicates n (1 \leq n \leq 500).
The i-th line of the following n lines contains string_i, which consists of up to 10 English lowercase letters.

The end of the input is 0, and this should not be processed.

Output

Print either yes or 
no in a line for each dataset, in the order of the input.
If all words in the dataset can be considered to be ordered lexicographically, print yes.
Otherwise, print no.

Sample Input

4
cba
cab
b
a
3
bca
ab
a
5
abc
acb
b
c
c
5
abc
acb
c
b
b
0

Output for the Sample Input

yes
no
yes
no



Sample input:
4
cba
cab
b
a
3
bca
ab
a
5
abc
acb
b
c
c
5
abc
acb
c
b
b
0


Sample output:
yes
no
yes
no

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        n = I()
        if n == 0:
            break

        a = [S() for _ in range(n)]
        e = collections.defaultdict(set)
        for c in string.ascii_lowercase:
            e[''].add(c)

        f = True
        for i in range(n):
            ai = a[i]
            for j in range(i+1,n):
                aj = a[j]
                for k in range(len(ai)):
                    if len(aj) <= k:
                        f = False
                        break
                    if ai[k] == aj[k]:
                        continue
                    e[ai[k]].add(aj[k])
                    break
        if not f:
            rr.append('no')
            continue

        v = collections.defaultdict(bool)
        v[''] = True

        def g(c):
            if v[c] == 2:
                return True
            if v[c] == 1:
                return False
            v[c] = 1
            for nc in e[c]:
                if not g(nc):
                    return False
            v[c] = 2
            return True

        for c in list(e.keys()):
            if v[c]:
                continue
            if not g(c):
                f = False
                break

        if f:
            rr.append('yes')
        else:
            rr.append('no')


    return '\n'.join(map(str,rr))



print(main())

Submission status: Accepted

Solution code:
def add_edge(node, adj_lst, adj_rev, s1, s2):
  ind = 0
  max_len = min(len(s1), len(s2))
  while ind < max_len and s1[ind] == s2[ind]:
    ind += 1
  if ind == max_len:
    if max_len < len(s1):
      return True
    return False
  c1 = ord(s1[ind]) - ord("a")
  c2 = ord(s2[ind]) - ord("a")
  adj_lst[c1].add(c2)
  adj_rev[c2].add(c1)
  node.add(c1)
  node.add(c2)
  return False
"""
def dfs(x, visited, adj_lst, order):
  visited[x] = True
  for to in adj_lst[x]:
    if not visited[to]:
      dfs(to, visited, adj_lst, order)
  order.append(x)

def dfs_rev(x, used, adj_rev):
  used.append(x)
  for to in adj_rev[x]:
    if not to in used:
      dfs_rev(x, used, adj_rev)
"""
while True:
  n = int(input())
  if n == 0:
    break
  
  lst = [input() for _ in range(n)]
  node = set()
  adj_lst = [set() for _ in range(26)]
  adj_rev = [set() for _ in range(26)]
  brunk_flag = False
  for i in range(n):
    for j in range(i + 1, n):
      brunk_flag = brunk_flag or add_edge(node, adj_lst, adj_rev, lst[i], lst[j])
  
  L = []
  visited = [False] * 26
  cycle_flag = False
  def visit(n):
    global cycle_flag
    if cycle_flag: return
    if visited[n] == 2:
      cycle_flag = True
    elif visited[n] == 0:
      visited[n] = 2
      for to in adj_lst[n]:
        visit(to)
      visited[n] = 1
      L.append(n)
  
  L = []
  for n in node:
    visit(n)
  if cycle_flag or brunk_flag:
    print("no")
  else:
    print("yes")

Submission status: Accepted

Solution code:
def add_edge(node, adj_lst, adj_rev, s1, s2):
  ind = 0
  max_len = min(len(s1), len(s2))
  while ind < max_len and s1[ind] == s2[ind]:
    ind += 1
  if ind == max_len:
    if max_len < len(s1):
      return True
    return False
  c1 = ord(s1[ind]) - ord("a")
  c2 = ord(s2[ind]) - ord("a")
  adj_lst[c1].add(c2)
  adj_rev[c2].add(c1)
  node.add(c1)
  node.add(c2)
  return False
def main():
  while True:
    n = int(input())
    if n == 0:
      break
    
    lst = [input() for _ in range(n)]
    node = set()
    adj_lst = [set() for _ in range(26)]
    adj_rev = [set() for _ in range(26)]
    blank_flag = False
    for i in range(n):
      for j in range(i + 1, n):
        blank_flag = blank_flag or add_edge(node, adj_lst, adj_rev, lst[i], lst[j])
    
    visited = [False] * 26
    cycle_flag = False
  
    def visit(n):
      ret = False
      if visited[n] == 2:
        return True
      elif visited[n] == 0:
        visited[n] = 2
        for to in adj_lst[n]:
          ret = ret or visit(to)
        visited[n] = 1
      return ret
    
    for n in node:
      cycle_flag = cycle_flag or visit(n)
    if cycle_flag or blank_flag:
      print("no")
    else:
      print("yes")

main()

Submission status: Accepted

Solution code:
def add_edge(node, adj_lst, s1, s2):
  ind = 0
  max_len = min(len(s1), len(s2))
  while ind < max_len and s1[ind] == s2[ind]:
    ind += 1
  if ind == max_len:
    return max_len < len(s1)

  c1 = ord(s1[ind]) - ord("a")
  c2 = ord(s2[ind]) - ord("a")
  adj_lst[c1].add(c2)
  node.add(c1)
  node.add(c2)
  return False

def visit(n, visited, adj_lst):
  ret = False
  if visited[n] == 2:
    return True
  elif visited[n] == 0:
    visited[n] = 2
    for to in adj_lst[n]:
      ret = ret or visit(to, visited, adj_lst)
    visited[n] = 1
  return ret
 
def main():
  while True:
    n = int(input())
    if n == 0:
      break
    
    lst = [input() for _ in range(n)]
    node = set()
    adj_lst = [set() for _ in range(26)]
    blank_flag = False
    for i in range(n):
      for j in range(i + 1, n):
        blank_flag = blank_flag or add_edge(node, adj_lst, lst[i], lst[j])
    if blank_flag:
      print("no")
      continue
    
    visited = [0] * 26
    cycle_flag = False
  
    for n in node:
      cycle_flag = cycle_flag or visit(n, visited, adj_lst)
    if cycle_flag:
      print("no")
    else:
      print("yes")

main()

Submission status: Accepted

Solution code:
graph = []

def init():
    global graph
    graph = [[False] * 26 + [True] for _ in xrange(27)]
    graph[26][26] = False

def atoi(c):#index
    if c == "#":
        return 26
    return ord(c) - ord("a")

def make_graph(L):
    global graph, count
    cur = 0
    L = [L[0]] + [L[i] for i in xrange(1, len(L)) if L[i] != L[i-1]]
    tmp = []
    for s1, s2 in zip(L, L[1:]):
        if s1[0] == s2[0]:
            tmp += [s1[1:], s2[1:]]
        else:
            if not tmp == []:
                make_graph(tmp)
            tmp = []
            graph[atoi(s2[0])][atoi(s1[0])] = True
    if not tmp == []:
        make_graph(tmp)

def check(start):
    stack = set([start])
    visited = [False] * 27
    while len(stack) != 0:
        cur = stack.pop()
        visited[cur] = True
        if graph[cur][start]:
            return False
        for i in xrange(27):
            if graph[cur][i] and not visited[i]:
                stack.add(i)
    return True

while True:
    n = input()
    if n == 0:
        break
    L = [raw_input() + "#" for _ in xrange(n)]
    init()
    make_graph(L)
    for i in xrange(27):
        if not check(i):
            print "no"
            break
    else:
        print "yes"

Submission status: Accepted

Solution code:
graph = []

def init():
    global graph
    graph = [[False] * 26 + [True] for _ in xrange(27)]
    graph[26][26] = False

def atoi(c):#index
    if c == "#":
        return 26
    return ord(c) - ord("a")

def make_graph(L):
    global graph
    cur = 0
    L = [L[0]] + [L[i] for i in xrange(1, len(L)) if L[i] != L[i-1]]
    tmp = []
    for s1, s2 in zip(L, L[1:]):
        if s1[0] == s2[0]:
            tmp += [s1[1:], s2[1:]]
        else:
            if not tmp == []:
                make_graph(tmp)
            tmp = []
            graph[atoi(s2[0])][atoi(s1[0])] = True
    if not tmp == []:
        make_graph(tmp)

def check(start):
    stack = set([start])
    visited = [False] * 27
    while len(stack) != 0:
        cur = stack.pop()
        visited[cur] = True
        if graph[cur][start]:
            return False
        for i in xrange(27):
            if graph[cur][i] and not visited[i]:
                stack.add(i)
    return True

while True:
    n = input()
    if n == 0:
        break
    L = [raw_input() + "#" for _ in xrange(n)]
    init()
    make_graph(L)
    for i in xrange(27):
        if not check(i):
            print "no"
            break
    else:
        print "yes"

Submission status: Accepted

Solution code:
graph = []

def init():
    global graph
    graph = [[False] * 26 + [True] for _ in xrange(27)]
    graph[26][26] = False

def atoi(c):#index
    if c == "#":
        return 26
    return ord(c) - ord("a")

def make_graph(L):
    global graph
    cur = 0
    L = [L[0]] + [L[i] for i in xrange(1, len(L)) if L[i] != L[i-1]] #
    #while "" in L:
    #    L.remove("")
    tmp = []
    for s1, s2 in zip(L, L[1:]):
        if s1[0] == s2[0]:
            tmp += [s1[1:], s2[1:]]
        else:
            if not tmp == []:
                make_graph(tmp)
            tmp = []
            graph[atoi(s2[0])][atoi(s1[0])] = True
    if not tmp == []:
        make_graph(tmp)

def check(start):
    stack = set([start])
    visited = [False] * 27
    while len(stack) != 0:
        cur = stack.pop()
        visited[cur] = True
        if graph[cur][start]:
            return False
        for i in xrange(27):
            if graph[cur][i] and not visited[i]:
                stack.add(i)
    return True

while True:
    n = input()
    if n == 0:
        break
    L = [raw_input() + "#" for _ in xrange(n)]
    init()
    make_graph(L)
    for i in xrange(27):
        if not check(i):
            print "no"
            break
    else:
        print "yes"

Submission status: Runtime Error

Solution code:
def add_edge(node, adj_lst, adj_rev, s1, s2):
  ind = 0
  max_len = min(len(s1), len(s2))
  while ind < max_len and s1[ind] == s2[ind]:
    ind += 1
  if ind == max_len:
    if max_len < len(s1):
      return True
    return False
  c1 = ord(s1[ind]) - ord("a")
  c2 = ord(s2[ind]) - ord("a")
  adj_lst[c1].add(c2)
  adj_rev[c2].add(c1)
  node.add(c1)
  node.add(c2)
  return False
def main():
  while True:
    n = int(input())
    if n == 0:
      break
    
    lst = [input() for _ in range(n)]
    node = set()
    adj_lst = [set() for _ in range(26)]
    adj_rev = [set() for _ in range(26)]
    blank_flag = False
    for i in range(n):
      for j in range(i + 1, n):
        blank_flag = blank_flag or add_edge(node, adj_lst, adj_rev, lst[i], lst[j])
    
    L = []
    visited = [False] * 26
    cycle_flag = False
  
    def visit(n):
      global cycle_flag
      if cycle_flag: return
      if visited[n] == 2:
        cycle_flag = True
      elif visited[n] == 0:
        visited[n] = 2
        for to in adj_lst[n]:
          visit(to)
        visited[n] = 1
        L.append(n)
    
    L = []
    for n in node:
      visit(n)
    if cycle_flag or blank_flag:
      print("no")
    else:
      print("yes")

main()

Submission status: Runtime Error

Solution code:
graph = []

def init():
    global graph
    graph = [[False] * 26 + [True] for _ in xrange(27)]
    graph[26][26] = False

def atoi(c):#index
    if c == "#":
        return 26
    return ord(c) - ord("a")

def make_graph(L):
    global graph
    tmp = []
    while "" in L:
        L.remove("")
    for s1, s2 in zip(L, L[1:]):
        if s1[0] == s2[0]:
            tmp += [s1[1:], s2[1:]]
        else:
            if not tmp == [] and not make_graph(tmp):
                return False
            tmp = []
            graph[atoi(s2[0])][atoi(s1[0])] = True
    if not tmp == [] and not make_graph(tmp):
        return False
    return True

def check(start):
    stack = set([start])
    visited = [False] * 27
    while len(stack) != 0:
        cur = stack.pop()
        visited[cur] = True
        if graph[cur][start]:
            return False
        for i in xrange(27):
            if graph[cur][i] and not visited[i]:
                stack.add(i)
    return True

while True:
    n = input()
    if n == 0:
        break
    L = [raw_input() + "#" for _ in xrange(n)]
    init()
    make_graph(L)
    for i in xrange(27):
        if not check(i):
            print "no"
            break
    else:
        print "yes"

Submission status: Runtime Error

Solution code:
graph = []

def init():
    global graph
    graph = [[False] * 26 + [True] for _ in xrange(27)]
    graph[26][26] = False

def atoi(c):#index
    if c == "#":
        return 26
    return ord(c) - ord("a")

def make_graph(L):
    global graph
    tmp = []
    while "" in L:
        L.remove("")
    for s1, s2 in zip(L, L[1:]):
        if s1[0] == s2[0]:
            tmp += [s1[1:], s2[1:]]
        else:
            if not tmp == []:
                make_graph(tmp)
            tmp = []
            graph[atoi(s2[0])][atoi(s1[0])] = True
    if not tmp == []:
        make_graph(tmp)

def check(start):
    stack = set([start])
    visited = [False] * 27
    while len(stack) != 0:
        cur = stack.pop()
        visited[cur] = True
        if graph[cur][start]:
            return False
        for i in xrange(27):
            if graph[cur][i] and not visited[i]:
                stack.add(i)
    return True

while True:
    n = input()
    if n == 0:
        break
    L = [raw_input() + "#" for _ in xrange(n)]
    init()
    make_graph(L)
    for i in xrange(27):
        if not check(i):
            print "no"
            break
    else:
        print "yes"