Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class V():
- def __init__(self, id):
- self.id = id
- self.nodes = []
- self.node_type = []
- def add_edge(self, v, type):
- self.nodes.append(v)
- self.node_type.append(type)
- def get_nodes(self):
- return self.nodes, self.node_type
- def n_dfs(v, vs):
- global used
- global gr
- global ans
- used[v] = True
- nodes, node_type = gr[v].get_nodes()
- for i in range(0, len(nodes)):
- if(nodes[i] == vs):
- if(node_type[i] == '+'):
- ans = '-'
- return '-'
- if(not used[nodes[i]]):
- if(node_type[i] == '+'):
- n_dfs(nodes[i], vs)
- if(ans == '-'):
- return '-'
- return '?'
- def dfs(v, vs):
- global used
- global gr
- global ans
- used[v] = True
- nodes, node_type = gr[v].get_nodes()
- for i in range(0, len(nodes)):
- if(nodes[i] == vs):
- if(node_type[i] == '+'):
- ans = '+'
- return '+'
- elif(node_type[i] == '-'):
- ans = '-'
- return '-'
- if(not used[nodes[i]]):
- if(node_type[i] == '+'):
- dfs(nodes[i], vs)
- elif(node_type[i] == '-'):
- n_dfs(nodes[i], vs)
- if(ans == '+'):
- return '+'
- elif(ans == '-'):
- return '-'
- return '?'
- n, k = list(map(str, input().strip().split(' ')))
- gr = []
- for i in range(0, int(n)):
- gr.append(V(i))
- for i in range(0, int(k)):
- z, v1, v2 = list(map(str, input().strip().split(' ')))
- v1 = int(v1)
- v2 = int(v2)
- v1 -= 1
- v2 -= 1
- if(z == '+'):
- gr[v1].add_edge(v2, '+')
- gr[v2].add_edge(v1, '+')
- elif(z == '-'):
- gr[v1].add_edge(v2, '-')
- gr[v2].add_edge(v1, '-')
- elif(z == '?'):
- used = []
- for i in range(0, int(n)):
- used.append(False)
- ans = ''
- print(dfs(v1, v2))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement