fork download
copy 
  1. n,m,k = map(int,raw_input().split())
  2. graph = {}
  3. for _ in range(m):
  4.     a,b = map(int,raw_input().split())
  5.     if a in graph:
  6.         graph[a].append(b)
  7.     else:
  8.         graph[a] = [b]
  9.     if b in graph:
  10.         graph[b].append(a)
  11.     else:
  12.         graph[b] = [a]
  13. specialNodes = sorted(map(int,raw_input().split()))
  14. isSpecial = [False for i in range(n+1)]
  15. for specialNode in specialNodes:
  16.     isSpecial[specialNode] = True
  17.  
  18. minDist = n+1
  19. for i in specialNodes:
  20.     visited = {}
  21.     visited[i] = True
  22.     stack = []
  23.     stackSize = 0
  24.     for child in graph[i]:
  25.         stack.append((child,1))
  26.         stackSize += 1
  27.     currentIndex = 0
  28.     while currentIndex < stackSize:
  29.         visited[stack[currentIndex][0]] = True
  30.         if isSpecial[stack[currentIndex][0]]:
  31.             minDist = min(stack[currentIndex][1],minDist)
  32.             break
  33.         elif stack[currentIndex][1] >= minDist:
  34.             break
  35.         else:
  36.             currentLevel = stack[currentIndex][1]
  37.             for child in graph[stack[currentIndex][0]]:
  38.                 if not(child in visited):
  39.                     stack.append((child,currentLevel+1))
  40.                     stackSize += 1
  41.             currentIndex += 1
  42.  
  43. minRadius = (minDist-1)/2
  44. ans = 0
  45. visited = [False for i in range(n+1)]
  46. def dfs(parentNode, currentNode, level):
  47.     global ans
  48.     if level > minRadius:
  49.         return
  50.     else:
  51.         ans += 1
  52.         visited[currentNode] = True
  53.         for child in graph[currentNode]:
  54.             if not(visited[child]):
  55.                 dfs(currentNode,child,level+1)
  56.  
  57. for node in specialNodes:
  58.     dfs(-1,node,0)
  59. print ans
Success #stdin #stdout 0s 23304KB
comments (?)
stdin
copy 
5 4 2
1 2
2 3
3 4
4 5
1 5
stdout
copy 
4
https://ideone.com/ld6or5
language:
Python (cpython 2.7.16)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!