Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #User function Template for python3
- from collections import defaultdict as dd,deque
- class Solution:
- def isCircle(self, n, A):
- adj={c:set() for w in A for c in w}
- tr={c:set() for w in A for c in w}
- for i in A:
- adj[i[0]].add(i[-1])
- tr[i[-1]].add(i[0])
- #print(adj)
- vis=set()
- def dfs(u,q):
- vis.add(u)
- for v in adj[u]:
- if v not in vis:
- dfs(v,q)
- q.append(u)
- q=deque()
- for i in A:
- if i[0] not in vis:
- dfs(i[0],q)
- #print(q)
- #print(adj)
- #print(adj)
- #print(tr)
- vis=set()
- def ndfs(u):
- vis.add(u)
- for v in tr[u]:
- if v not in vis:
- ndfs(v)
- comp=0
- while q:
- t=q.pop()
- if t not in vis:
- ndfs(t)
- comp+=1
- #print(comp)
- return 1 if comp==1 else 0
- #{
- # Driver Code Starts
- #Initial Template for Python 3
- import sys
- sys.setrecursionlimit(10**6)
- if __name__ == '__main__':
- t = int(input())
- for _ in range (t):
- N = int(input())
- A = input().split()
- ob = Solution()
- print(ob.isCircle(N, A))
- # } Driver Code Ends
Advertisement
Add Comment
Please, Sign In to add comment