fork download
copy 
  1. import sys
  2. from collections import defaultdict
  3.  
  4. def main():
  5.     N = int(sys.stdin.readline())
  6.     adj = defaultdict(set)
  7.  
  8.     for _ in range(N):
  9.         a, b = map(int, sys.stdin.readline().split())
  10.         adj[a].add(b)
  11.         adj[b].add(a)
  12.  
  13.     THRESHOLD = int(N ** 0.5)
  14.     heavy = {u for u in adj if len(adj[u]) > THRESHOLD}
  15.  
  16.     # Precompute ffriend relation among heavy nodes
  17.     # For each heavy node h, for each neighbor z of h, mark (h, neighbor of z) as ffriends
  18.     heavy_ff = defaultdict(set)
  19.     for h in heavy:
  20.         for z in adj[h]:
  21.             for w in adj[z]:
  22.                 if w != h and w not in adj[h]:
  23.                     heavy_ff[h].add(w)
  24.  
  25.     M = int(sys.stdin.readline())
  26.  
  27.     for _ in range(M):
  28.         line = sys.stdin.readline().split()
  29.         qt = line[0]
  30.  
  31.         if qt == 'N':
  32.             x = int(line[1])
  33.             print(len(adj[x]))
  34.  
  35.         elif qt == 'F':
  36.             x, y = int(line[1]), int(line[2])
  37.             print('True' if y in adj[x] else 'False')
  38.  
  39.         else:  # FF
  40.             x, y = int(line[1]), int(line[2])
  41.  
  42.             if y in adj[x]:
  43.                 print('False')
  44.                 continue
  45.  
  46.             if x in heavy and y in heavy:
  47.                 print('True' if y in heavy_ff[x] else 'False')
  48.             else:
  49.                 # At least one is light, iterate the lighter one
  50.                 sx, sy = adj[x], adj[y]
  51.                 if len(sx) > len(sy):
  52.                     sx, sy = sy, sx
  53.                 for z in sx:
  54.                     if z in sy:
  55.                         print('True')
  56.                         break
  57.                 else:
  58.                     print('False')
  59.  
  60. main()
Success #stdin #stdout 0.09s 13976KB
comments (?)
stdin
copy 
3
0 1
1 2
2 3
6
N 1
FF 0 2
F 3 4
FF 0 3
N 5
F 3 2
stdout
copy 
2
True
False
False
0
True
https://ideone.com/ZWFfQX
language:
Python 3 (python  3.12)
created:
21 hours 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!