Competitive_Coding/PythonGraph.py at master · Ankitr19/Competitive_Coding · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
fromcollectionsimportdefaultdict

classGraph:

def__init__(self):

self.graph=defaultdict(list)

defaddEdge(self,u,v):
self.graph[u].append(v)

defDFSUtil(self,v,visited,ct):

visited[v] =ct
#print (v)
ct=ct+1
foriinself.graph[v]:
#print(i)
ifvisited[i]==0:
self.DFSUtil(i,visited,ct)

defDFS(self,v,r,l,h):

visited= [0]*(10007)
#print(len(visited))
ct=1
mx=-1
ans=-1
self.DFSUtil(v,visited,ct)
foriinrange(0,10007):
if(mx<visited[i] andvisited[i]!=0):
mx=visited[i]
ans=i
print(ans)


t=int(input())
while(t>0):

n=int(input())
g=Graph()
mini=10009
maxi=-1
foriinrange(0,n-1):
a,b=input().split()
a=int(a)
b=int(b)
g.addEdge(a,b)
mini=min(a,b)
maxi=max(a,b)
#000000#000000
start=int(input())
rangei=int(maxi) -int(mini)

#print(start)
g.DFS(start,rangei,mini,maxi)
#for i in range(mini,maxi+1):
#	print(g.visited[i])
#g.printGraph()
t=t-1