Advertisement
Iam_Sandeep

Untitled

Jun 29th, 2022
374
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #User function Template for python3
  2. from collections import defaultdict as dd,deque
  3. class Solution:
  4.     def isCircle(self, n, A):
  5.         adj={c:set() for w in A for c in w}
  6.         tr={c:set() for w in A for c in w}
  7.         for i in A:
  8.             adj[i[0]].add(i[-1])
  9.             tr[i[-1]].add(i[0])
  10.         #print(adj)
  11.         vis=set()
  12.        
  13.         def dfs(u,q):
  14.             vis.add(u)
  15.             for v in adj[u]:
  16.                 if v not in vis:
  17.                     dfs(v,q)
  18.             q.append(u)
  19.         q=deque()
  20.        
  21.        
  22.         for i in A:
  23.             if i[0] not in vis:
  24.                 dfs(i[0],q)
  25.         #print(q)    
  26.         #print(adj)
  27.        
  28.  
  29.  
  30.         #print(adj)
  31.         #print(tr)
  32.         vis=set()
  33.        
  34.         def ndfs(u):
  35.             vis.add(u)
  36.             for v in tr[u]:
  37.                 if v not in vis:
  38.                     ndfs(v)
  39.         comp=0
  40.        
  41.         while q:
  42.             t=q.pop()
  43.             if t not in vis:
  44.                 ndfs(t)
  45.                 comp+=1
  46.         #print(comp)
  47.         return 1 if comp==1 else 0
  48.            
  49.  
  50. #{
  51. #  Driver Code Starts
  52. #Initial Template for Python 3
  53.  
  54. import sys
  55. sys.setrecursionlimit(10**6)
  56. if __name__ == '__main__':
  57.     t = int(input())
  58.     for _ in range (t):
  59.         N = int(input())
  60.         A = input().split()
  61.        
  62.         ob = Solution()
  63.         print(ob.isCircle(N, A))
  64. # } Driver Code Ends
Advertisement
RAW Paste Data Copied
Advertisement