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:
11.         vis=set()
12.
13.         def dfs(u,q):
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)
27.
28.
29.
31.         #print(tr)
32.         vis=set()
33.
34.         def ndfs(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