fork download
copy 
  1. import sys
  2. from collections import defaultdict
  3. #cycle checking function
  4. def cycle_exists(G):                     
  5.     color = { u : "white" for u in G  }  
  6.     found_cycle = [False]                
  7.     for u in G:                          
  8.         if color[u] == "white":
  9.             dfs_visit(G, u, color, found_cycle)
  10.         if found_cycle[0]:
  11.             break
  12.     return found_cycle[0]
  13. def dfs_visit(G, u, color, found_cycle):
  14.     if found_cycle[0]:                          
  15.         return
  16.     color[u] = "gray"                           
  17.     for v in G[u]:                              
  18.         if color[v] == "gray":                   
  19.             found_cycle[0] = True       
  20.             return
  21.         if color[v] == "white":                   
  22.             dfs_visit(G, v, color, found_cycle)
  23.     color[u] = "black"  
  24.  
  25. t=int(input())
  26. for ii in range(t):
  27.     mat=[]
  28.     char_dict=dict()
  29.     r,c=map(int,input().split())
  30.     for j in range(r):
  31.         col=[i for i in input()]
  32.         mat.append(col)
  33.     graph=defaultdict(set)
  34.     #creates the graph and a dictionary to store all the unique characters
  35.     for j in range(r-2,-1,-1):
  36.         for k in range(c):
  37.             char_dict[mat[j][k]]=0
  38.             char_dict[mat[j+1][k]]=0
  39.             if mat[j][k]!=mat[j+1][k]:
  40.                 graph[mat[j][k]].add(mat[j+1][k])
  41.                 if mat[j+1][k] not in graph:
  42.                     graph[mat[j+1][k]]=set()
  43. 	#if r==1, simply print all the unique elements in the row
  44.     if r==1:
  45.         col=''.join(map(str,set(col)))
  46.         sys.stdout.write("Case #"+str(ii+1)+':'+' '+col+'\n')
  47.     #if cycle exists, print -1
  48.     elif (cycle_exists(graph)):
  49.         sys.stdout.write("Case #"+str(ii+1)+':'+' '+str(-1)+'\n')
  50.     #topological sort
  51.     else:
  52.         OBSERVE = 0
  53.         CHECK = 1
  54.         topsort=[]
  55.         for i in char_dict:
  56.             if char_dict[i]==0:
  57.                 stack = [(OBSERVE, i, 0)]
  58.                 while len(stack):
  59.                     state, vertex, parent = stack.pop()
  60.                     char_dict[vertex]=1
  61.                     if state == OBSERVE:
  62.                         stack.append((CHECK, vertex, parent))
  63.                         for child in graph[vertex]:
  64.                             if char_dict[child]!=1:
  65.                                 stack.append((OBSERVE, child, vertex))
  66.                     else:
  67.                             topsort.append(vertex)
  68.         topsort=''.join(map(str,topsort))
  69.         sys.stdout.write("Case #"+str(ii+1)+':'+' '+topsort+'\n')
  70.  
  71.  
Success #stdin #stdout 0.03s 9368KB
comments (?)
stdin
copy 
4
4 6
ZOAAMM
ZOAOMM
ZOOOOM
ZZZZOM
4 4
XXOO
XFFO
XFXO
XXXO
5 3
XXX
XPX
XXX
XJX
XXX
3 10
AAABBCCDDE
AABBCCDDEE
AABBCCDDEE
stdout
copy 
Case #1: ZOMA
Case #2: -1
Case #3: -1
Case #4: EDCBA
https://ideone.com/QXkmJ7
language:
Python 3 (python  3.9.5)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!