Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class DisjointSet:
- _disjoint_set = list()
- def __init__(self, init_arr):
- self._disjoint_set = []
- if init_arr:
- for item in list(set(init_arr)):
- self._disjoint_set.append([item])
- def _find_index(self, elem):
- for item in self._disjoint_set:
- if elem in item:
- return self._disjoint_set.index(item)
- return None
- def find(self, elem):
- for item in self._disjoint_set:
- if elem in item:
- return self._disjoint_set[self._disjoint_set.index(item)]
- return None
- def union(self,elem1, elem2):
- index_elem1 = self._find_index(elem1)
- index_elem2 = self._find_index(elem2)
- if index_elem1 != index_elem2 and index_elem1 is not None and index_elem2 is not None:
- self._disjoint_set[index_elem2] = self._disjoint_set[index_elem2]+self._disjoint_set[index_elem1]
- del self._disjoint_set[index_elem1]
- return self._disjoint_set
- def get(self):
- return self._disjoint_set
- x=input().split()
- n=int(x[0])
- k=int(x[1])
- s=[]
- for i in range(1,n+1):
- s.append(int(i))
- ways_set = DisjointSet(s)
- for i in range(k):
- request=input().split()
- typer=request[0]
- city1=int(request[1])
- city2=int(request[2])
- if(typer=='+'):
- ways_set.union(city1, city2)
- if(typer=='?'):
- if(ways_set.find(city1)!=ways_set.find(city2)):
- print('-')
- else:
- print('+')
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement