a-new-order

Consider a new order of english alphabets (a to z), that we are not aware of.
What we have though, dictionary of words, ordered according to the new order.

Our task is to give each alphabet a rank, ordered list of words.
The rank of an alphabet is the minimum integer R that can be given to it, such that:

if alphabet Ai has rank Ri and alphabet Aj has Rj, then
Rj > Ri if and only if Aj > Ai
Rj < Ri if and only if Aj < Ai

Points to note:
We only need to find the order of alphabets that are present in the words
There might be some cases where a strict ordering of words cannot be inferred completely, given the limited information. In that case, give the least possible Rank to every alphabet
It can be assumed that there will be no direct or indirect conflict in different inferences got from the input

Input:
First line consists of integer 'W', the number of words. 1 ≤ W ≤ 100
Second line onwards, there are 'W' lines, given ordered list of words. The words will be non-empty, and will be of length ≤ 20 characters. Also all the characters will be lowercase alphabets, a to z

Output:

The alphabets, in order of their Rank, for alphabets with the same rank, print them in the order as we know it today

Examples

1)

Input:
2
ba
ab

Output:
b
a

Explanation: ab comes after ba implies that b < a

2)

Input:
3
abc
aca
ca

Ouput:
ab
c

Explanation: from the first 2 words, we know b < c, and from the last 2 words, we know a < c. We don't have an ordering between a and b, so we give both of them the same rank, and print them in the order as we know today: ab

SAMPLE INPUT
6
aaabc
aaade
bacd
cde
cda
cca

SAMPLE OUTPUT
e
a
b
d
c

Source: hackerearth | Difficulty: EASY
Tags: Graph algorithms

Graph traversal


Solutions:
Adj = {}
root = {}
def add(a, b):
	if a in Adj:
		Adj[a]["child"].add(b)
	else:
		Adj[a] = {"rank":0, "child":set([b])}
	if b in Adj:
		if b in root:
			del root[b]
		
		return
	else:
		if b in root:
			del root[b]
		Adj[b] = {"rank":0, "child":set()}

def addv(a):
	if a in Adj:
		return
	else:
		Adj[a] = {"rank":0, "child":set()}
		root[a] = ""


def process(words, n):
	
	for woe in words:
		for i in range(len(woe)):
			addv(woe[i])

	lev = 0
	flags = False
	for i in range(n-1):
		
		lev = 0

		while words[i][lev] == words[i+1][lev]:
			lev+=1
			#print lev
			#print len(words[i])
			if len(words[i]) <= lev:
				flags = True
				break

		if flags == True:
			flags = False
			continue

		add(words[i][lev], words[i+1][lev])

'''
['achmopru', 'bn', 'd', 'ev', 'fisx', 'lty']
['achmopru', 'bnv', 'dx', 'e', 'fis', 'lty']
'''
#ans = {"merg":[], "mergAdv":[]}
def mergAdv():

	rank = {}
	
	max = 0
	cur = []
	for ch in root:
		rank[ch] = 0
		cur.append(ch)
		
		while cur:
			current = cur[0]
			del cur[0]
			
			for c in Adj[current]["child"]:
				cur.append(c)
				if c in rank:
					if rank[c] < rank[current]+1:
						rank[c] = rank[current]+1
				else: 
					rank[c] = rank[current]+1
				
				if rank[c] > max:
					max = rank[c]

	top = ["" for x in range(max+1) ]
	
		
	for ch in Adj:
		
		i = rank[ch]
		if top[i] == "":
			top[i] = ch
		else:
			top[i] = "".join(sorted(top[i] + ch))
	
	for i in top:
		if i!="":
			#ans["mergAdv"].append(i)
			print(i)
	

N = int(input())
words = []
for i in range(N):
	words.append(input())
process(words, N)
mergAdv()



Adj = {}
root = {}
def add(a, b):
	if a in Adj:
		Adj[a]["child"].add(b)
	else:
		Adj[a] = {"rank":0, "child":set([b])}
	if b in Adj:
		if b in root:
			del root[b]
		
		return
	else:
		if b in root:
			del root[b]
		Adj[b] = {"rank":0, "child":set()}
 
def addv(a):
	if a in Adj:
		return
	else:
		Adj[a] = {"rank":0, "child":set()}
		root[a] = ""
 
 
def process(words, n):
	
	for woe in words:
		for i in range(len(woe)):
			addv(woe[i])
 
	lev = 0
	flags = False
	for i in range(n-1):
		
		lev = 0
 
		while words[i][lev] == words[i+1][lev]:
			lev+=1
			#print lev
			#print len(words[i])
			if len(words[i]) <= lev:
				flags = True
				break
 
		if flags == True:
			flags = False
			continue
 
		add(words[i][lev], words[i+1][lev])
 
'''
['achmopru', 'bn', 'd', 'ev', 'fisx', 'lty']
['achmopru', 'bnv', 'dx', 'e', 'fis', 'lty']
'''
#ans = {"merg":[], "mergAdv":[]}
def mergAdv():
 
	rank = {}
	
	max = 0
	cur = []
	for ch in root:
		rank[ch] = 0
		cur.append(ch)
		
		while cur:
			current = cur[0]
			del cur[0]
			
			for c in Adj[current]["child"]:
				cur.append(c)
				if c in rank:
					if rank[c] < rank[current]+1:
						rank[c] = rank[current]+1
				else: 
					rank[c] = rank[current]+1
				
				if rank[c] > max:
					max = rank[c]
 
	top = ["" for x in range(max+1) ]
	
		
	for ch in Adj:
		
		i = rank[ch]
		if top[i] == "":
			top[i] = ch
		else:
			top[i] = "".join(sorted(top[i] + ch))
	
	for i in top:
		if i!="":
			#ans["mergAdv"].append(i)
			print(i)
	
 
N = int(input())
words = []
for i in range(N):
	words.append(input())
process(words, N)
mergAdv()


Adj = {}
root = {}
def add(a, b):
	if a in Adj:
		Adj[a]["child"].add(b)
	else:
		Adj[a] = {"rank":0, "child":set([b])}
	if b in Adj:
		if b in root:
			del root[b]
		#if a not in Adj[b][parent]:
			#Adj[b][rank] += 1
			#Adj[b][parent].add(a)
		return
	else:
		if b in root:
			del root[b]
		Adj[b] = {"rank":0, "child":set()}

def addv(a):
	if a in Adj:
		return
	else:
		Adj[a] = {"rank":0, "child":set()}
		root[a] = ""


def process(words, n):
	
	for woe in words:
		for i in range(len(woe)):
			addv(woe[i])

	lev = 0
	flags = False
	for i in range(n-1):
		#print words[i], " : first"
		#print words[i+1], " : second"
		lev = 0

		while words[i][lev] == words[i+1][lev]:
			lev+=1
			#print lev
			#print len(words[i])
			if len(words[i]) <= lev:
				flags = True
				break

		if flags == True:
			flags = False
			continue

		add(words[i][lev], words[i+1][lev])

'''
['achmopru', 'bn', 'd', 'ev', 'fisx', 'lty']
['achmopru', 'bnv', 'dx', 'e', 'fis', 'lty']
'''
ans = {"merg":[], "mergAdv":[]}
def mergAdv():

	rank = {}
	
	max = 0
	cur = []
	for ch in root:
		rank[ch] = 0
		cur.append(ch)
		
		while cur:
			current = cur[0]
			del cur[0]
			#child = 
			
			for c in Adj[current]["child"]:
				cur.append(c)
				if c in rank:
					if rank[c] < rank[current]+1:
						rank[c] = rank[current]+1
				else: 
					rank[c] = rank[current]+1
				#Adj[c]["rank"] = Adj[current]["rank"] + 1
				#if Adj[c]["rank"] > max:
				if rank[c] > max:
					max = rank[c]
		
		
	#print rank
			
		
	top = ["" for x in range(max+1) ]
	#for ch in Adj:
		
	for ch in Adj:
		#print Adj[ch]["rank"]
		i = rank[ch]
		if top[i] == "":
			top[i] = ch
		else:
			top[i] = "".join(sorted(top[i] + ch))
	
	for i in top:
		if i!="":
			ans["mergAdv"].append(i)
			print(i)
	
def merg():
	
	for ch in Adj:
		cur = list(Adj[ch]["child"])
		done = set()
		#i=-1
		while cur:
			#i+=1
			c = cur[0]
			
			del cur[0]
			
			if c not in done:
				for cha in Adj[c]["child"]:
					cur += cha
					add(ch, cha)



			done.add(c)
	max = 0
	for ch in Adj:
		for c in Adj[ch]["child"]:
			
			Adj[c]["rank"] += 1
			if Adj[c]["rank"] > max:
				max = Adj[c]["rank"]
	top = ["" for x in range(max+1) ]
	#for ch in Adj:
		
	for ch in Adj:
		#print Adj[ch]["rank"]
		i = Adj[ch]["rank"]
		if top[i] == "":
			top[i] = ch
		else:
			top[i] = "".join(sorted(top[i] + ch))
	
	for i in top:
		if i!="":
			ans["merg"].append(i)

N = int(input())
words = []
for i in range(N):
	words.append(input())
process(words, N)
mergAdv()
#merg()
#print Adj
#print ans["merg"]
#print ans["mergAdv"]