Advertisement
Guest User

Untitled

a guest
Nov 13th, 2019
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.29 KB | None | 0 0
  1. class DisjointSet:
  2.     _disjoint_set = list()
  3.  
  4.     def __init__(self, init_arr):
  5.         self._disjoint_set = []
  6.         if init_arr:
  7.             for item in list(set(init_arr)):
  8.                 self._disjoint_set.append([item])
  9.  
  10.     def _find_index(self, elem):
  11.         for item in self._disjoint_set:
  12.             if elem in item:
  13.                 return self._disjoint_set.index(item)
  14.         return None
  15.  
  16.     def find(self, elem):
  17.         for item in self._disjoint_set:
  18.             if elem in item:
  19.                 return self._disjoint_set[self._disjoint_set.index(item)]
  20.         return None
  21.    
  22.     def union(self,elem1, elem2):
  23.         index_elem1 = self._find_index(elem1)
  24.         index_elem2 = self._find_index(elem2)
  25.         if index_elem1 != index_elem2 and index_elem1 is not None and index_elem2 is not None:
  26.             self._disjoint_set[index_elem2] = self._disjoint_set[index_elem2]+self._disjoint_set[index_elem1]
  27.             del self._disjoint_set[index_elem1]
  28.         return self._disjoint_set
  29.        
  30.     def get(self):
  31.         return self._disjoint_set
  32. x=input().split()
  33. n=int(x[0])
  34. k=int(x[1])
  35. s=[]
  36. for i in range(1,n+1):
  37.     s.append(int(i))
  38. ways_set = DisjointSet(s)
  39. for i in range(k):
  40.     request=input().split()
  41.     typer=request[0]
  42.     city1=int(request[1])
  43.     city2=int(request[2])
  44.     if(typer=='+'):
  45.         ways_set.union(city1, city2)
  46.     if(typer=='?'):
  47.         if(ways_set.find(city1)!=ways_set.find(city2)):
  48.             print('-')
  49.         else:
  50.             print('+')
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement