FilesExpand file tree

 main

/

Tree_Diameter.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

44 lines (34 loc) · 1.04 KB

 main

/

Tree_Diameter.py

Copy path

Top

File metadata and controls

• Code
• Blame

44 lines (34 loc) · 1.04 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

####################################################################################

# Please consider trying a few more times before referring to this code.

# Code might be incorrect - TLE / Wrong Answer (especially filenames with _1 , _2)

# Pedagogical > Pythonic

####################################################################################

from collections import defaultdict

I = lambda : map(int, input().split())

n = int(input())

adj = defaultdict(list)

for _ in range(n - 1):

a, b = I()

adj[a].append(b)

adj[b].append(a)

# 2 dfs

depth = [0] * (n + 1)

def dfs(i):

vis = [False] * (n + 1)

stack = [i]

while stack:

u = stack[-1]

if not vis[u]:

vis[u] = True

for v in adj[u]:

if not vis[v]:

stack.append(v)

depth[v] = depth[u] + 1

else:

stack.pop()

dfs(1)

b = depth.index(max(depth))

depth = [0] * (n + 1)

dfs(b)

print(max(depth))

# I once again ask you to try a few more times before referring here