Advertisement
Guest User

14/40

a guest
Nov 13th, 2019
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.61 KB | None | 0 0
  1. class V():
  2.     def __init__(self, id):
  3.         self.id = id
  4.         self.nodes = []
  5.         self.node_type = []
  6.  
  7.     def add_edge(self, v, type):
  8.         self.nodes.append(v)
  9.         self.node_type.append(type)
  10.  
  11.     def get_nodes(self):
  12.         return self.nodes, self.node_type
  13.  
  14. def n_dfs(v, vs):
  15.     global used
  16.     global gr
  17.     global ans
  18.     used[v] = True
  19.     nodes, node_type = gr[v].get_nodes()
  20.    
  21.     for i in range(0, len(nodes)):
  22.        
  23.         if(nodes[i] == vs):
  24.             if(node_type[i] == '+'):
  25.                 ans = '-'
  26.                 return '-'
  27.  
  28.         if(not used[nodes[i]]):
  29.             if(node_type[i] == '+'):
  30.                 n_dfs(nodes[i], vs)
  31.  
  32.     if(ans == '-'):
  33.         return '-'
  34.    
  35.     return '?'
  36.  
  37. def dfs(v, vs):
  38.     global used
  39.     global gr
  40.     global ans
  41.     used[v] = True
  42.     nodes, node_type = gr[v].get_nodes()
  43.    
  44.     for i in range(0, len(nodes)):
  45.         if(nodes[i] == vs):
  46.             if(node_type[i] == '+'):
  47.                 ans = '+'
  48.                 return '+'
  49.             elif(node_type[i] == '-'):
  50.                 ans = '-'
  51.                 return '-'
  52.  
  53.         if(not used[nodes[i]]):
  54.             if(node_type[i] == '+'):
  55.                 dfs(nodes[i], vs)
  56.             elif(node_type[i] == '-'):
  57.                 n_dfs(nodes[i], vs)
  58.  
  59.     if(ans == '+'):
  60.         return '+'
  61.     elif(ans == '-'):
  62.         return '-'
  63.    
  64.     return '?'
  65.  
  66. n, k = list(map(str, input().strip().split(' ')))
  67. gr = []
  68.  
  69. for i in range(0, int(n)):
  70.             gr.append(V(i))
  71.  
  72. for i in range(0, int(k)):
  73.     z, v1, v2 = list(map(str, input().strip().split(' ')))
  74.  
  75.     v1 = int(v1)
  76.     v2 = int(v2)
  77.     v1 -= 1
  78.     v2 -= 1
  79.  
  80.     if(z == '+'):
  81.         gr[v1].add_edge(v2, '+')
  82.         gr[v2].add_edge(v1, '+')
  83.     elif(z == '-'):
  84.         gr[v1].add_edge(v2, '-')
  85.         gr[v2].add_edge(v1, '-')
  86.     elif(z == '?'):
  87.         used = []
  88.         for i in range(0, int(n)):
  89.             used.append(False)
  90.         ans = ''
  91.         print(dfs(v1, v2))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement