Instantly share code, notes, and snippets.

# aymanfarhat/karger.py Last active Apr 25, 2018

Implementation of Karger's algorithm in Python. Randomized algorithm for computing minimum cuts in a connected graph. Input file source is Coursera's Algo 1 course HW3: http://spark-public.s3.amazonaws.com/algo1/programming_prob/kargerMinCut.txt
 import re import random # Load the file into a graph represented by a dict of lists def load_graph(): g = {} f = open('kargerMinCut.txt') lines = f.readlines() f.close() lines = map(lambda s: re.sub('\s+',' ',str(s.strip('\r\n'))).strip(),lines) lines = map(lambda s: s.split(' '),lines) for line in lines: g[int(line[0])] = map(lambda s: int(s),line[1:]) return g # Contract an edge between 2 vertices def contract_edge(edge): global g # merge v2 into v1 and remove v2 from graph v1l = g[edge[0]] v1l.extend(g[edge[1]]) del g[edge[1]] #replace all occurnces of v2 value with v1 for k, l in g.iteritems(): g[k] = [edge[0] if x == edge[1] else x for x in g[k]] # Remove all edges of v1 to itself(loops) g[edge[0]] = [x for x in g[edge[0]] if x != edge[0]] # Gets a random edge available in the current graph def get_random_edge(): v1 = g.keys() [random.randint(0,len(g)-1)] v2 = g[v1] [random.randint(0,len(g[v1])-1)] return (v1,v2) minlist = [] # Repeat 10 times to get a minimum for i in xrange(0,20): g = load_graph() # Keep contracting the graph until we have 2 vertices while(len(g) > 2): contract_edge(get_random_edge()) minlist.append(len(g[g.keys()[0]])) print min(minlist)
 1 37 79 164 155 32 87 39 113 15 18 78 175 140 200 4 160 97 191 100 91 20 69 198 196 2 123 134 10 141 13 12 43 47 3 177 101 179 77 182 117 116 36 103 51 154 162 128 30 3 48 123 134 109 41 17 159 49 136 16 130 141 29 176 2 190 66 153 157 70 114 65 173 104 194 54 4 91 171 118 125 158 76 107 18 73 140 42 193 127 100 84 121 60 81 99 80 150 55 1 35 23 93 5 193 156 102 118 175 39 124 119 19 99 160 75 20 112 37 23 145 135 146 73 35 6 155 56 52 120 131 160 124 119 14 196 144 25 75 76 166 35 87 26 20 32 23 7 156 185 178 79 27 52 144 107 78 22 71 26 31 15 56 76 112 39 8 113 93 8 185 155 171 178 108 64 164 53 140 25 100 133 9 52 191 46 20 150 144 39 62 131 42 119 127 31 7 9 91 155 8 160 107 132 195 26 20 133 39 76 100 78 122 127 38 156 191 196 115 10 190 184 154 49 2 182 173 170 161 47 189 101 153 50 30 109 177 148 179 16 163 116 13 90 185 11 123 134 163 41 12 28 130 13 101 83 77 109 114 21 82 88 74 24 94 48 33 12 161 109 169 21 24 36 65 50 2 101 159 148 54 192 88 47 11 142 43 70 182 177 179 189 194 33 13 161 141 157 44 83 90 181 41 2 176 10 29 116 134 182 170 165 173 190 159 47 82 111 142 72 154 110 21 103 130 11 33 138 152 14 91 156 58 122 62 113 107 73 137 25 19 40 6 139 150 46 37 76 39 127 15 149 58 68 52 39 67 121 191 1 45 100 18 118 174 40 85 196 122 42 193 119 139 26 127 145 135 57 38 7 16 48 10 36 187 43 3 114 173 111 142 129 88 189 117 128 147 141 194 180 106 167 179 66 74 136 51 59 17 48 123 134 36 163 3 44 117 167 161 152 95 170 83 180 77 65 72 109 47 43 88 159 197 28 194 181 49 18 193 149 56 62 15 160 67 191 140 52 178 96 107 132 1 145 89 198 4 26 73 151 126 34 115 19 156 80 178 164 108 84 71 174 40 62 113 22 89 45 91 126 195 144 5 14 172 20 185 122 171 56 8 52 73 191 67 126 9 119 1 89 79 107 96 31 75 55 5 6 34 23 21 188 187 12 173 180 197 138 167 63 111 95 13 192 116 94 114 105 49 177 51 130 90 11 50 66 157 176 22 156 27 32 131 7 56 53 81 149 23 100 146 115 26 175 121 96 75 57 39 119 71 132 19 150 140 93 23 91 122 124 22 200 195 145 5 69 125 55 68 156 20 58 191 4 57 149 6 24 123 134 161 163 169 72 116 167 30 33 77 162 143 159 187 63 184 130 28 50 153 12 148 11 53 25 193 185 79 108 8 158 87 73 81 115 39 64 178 132 27 68 127 84 14 52 200 97 6 93 26 193 58 27 108 52 144 160 18 84 81 22 75 139 166 15 107 198 131 7 9 133 6 27 156 139 144 166 112 100 26 174 31 42 75 158 122 81 22 7 58 73 89 115 39 25 200 69 169 28 134 188 24 184 159 29 72 114 152 116 169 173 141 17 111 61 192 90 11 177 179 77 33 66 83 136 29 48 134 188 13 47 88 3 82 92 28 194 50 192 189 123 199 177 147 43 106 148 197 77 103 129 181 30 165 123 10 24 41 187 47 168 92 148 197 101 50 2 179 111 130 77 153 199 70 31 27 171 56 131 146 139 191 89 20 108 38 71 75 69 196 149 97 8 86 98 7 32 156 149 171 62 22 185 35 124 56 38 158 97 53 121 160 1 191 58 89 127 87 120 39 99 84 60 151 174 6 33 48 161 109 141 24 187 47 88 168 183 110 103 95 116 28 12 11 13 83 134 63 34 37 122 171 118 76 131 166 137 40 46 97 87 80 164 127 18 62 52 20 139 35 79 164 125 32 107 137 75 121 85 55 69 45 193 132 4 5 200 135 76 139 198 6 36 165 188 17 106 88 16 177 110 147 154 159 179 136 41 50 141 66 162 152 168 184 12 43 72 180 190 77 2 170 61 122 37 193 149 39 121 191 115 146 52 127 79 198 58 125 38 34 1 76 89 164 97 86 178 108 87 84 124 98 174 195 14 5 57 196 186 38 193 37 86 32 76 107 73 85 127 100 46 89 31 57 96 158 99 160 45 15 9 39 193 37 122 102 8 158 32 87 85 81 200 60 5 27 155 1 58 150 15 113 76 84 22 25 151 139 100 14 145 9 7 40 91 156 122 79 118 125 52 175 87 15 81 166 132 121 19 14 160 34 78 71 41 36 169 184 116 163 106 189 11 104 61 30 123 129 111 3 47 49 154 161 152 13 153 65 92 183 177 162 95 54 70 108 42 178 79 27 53 171 164 102 52 87 113 15 191 131 91 62 193 8 122 89 56 4 127 145 112 43 165 161 12 70 199 54 17 190 16 153 141 36 47 44 194 110 82 189 2 148 183 29 130 94 170 51 61 59 44 188 163 169 17 13 43 114 173 142 154 103 129 181 105 157 148 182 101 110 66 176 49 45 156 80 149 58 178 53 108 68 56 125 15 93 75 135 174 198 81 166 113 100 19 89 35 97 38 46 193 58 86 122 155 8 175 160 99 127 67 14 150 144 126 146 34 131 55 38 196 47 123 10 109 41 17 12 43 116 59 33 13 2 187 165 88 117 29 30 176 147 180 101 130 194 50 94 152 70 48 180 128 188 197 105 51 94 190 116 29 183 114 153 33 16 49 3 63 184 17 141 168 179 162 11 66 83 193 49 48 123 10 186 141 41 168 3 148 142 179 21 136 109 44 117 17 103 187 74 50 165 123 10 188 36 169 24 187 12 65 29 167 47 21 134 130 111 168 77 116 138 106 66 30 51 165 48 109 141 163 159 92 190 143 2 21 138 43 59 192 117 16 184 104 169 52 37 178 8 6 15 200 133 80 102 96 40 119 164 166 127 151 20 42 7 26 76 18 73 99 78 25 132 139 191 150 34 53 156 122 102 193 137 133 42 62 45 64 60 78 160 132 155 56 144 131 196 178 125 8 32 113 22 98 121 198 24 54 123 187 12 43 168 65 129 130 147 95 41 61 59 141 3 138 114 199 66 110 55 68 56 125 113 73 78 200 46 131 85 107 89 185 60 84 4 35 99 171 71 20 23 56 193 122 53 108 45 55 18 125 86 171 79 6 85 133 80 140 96 31 107 20 32 87 120 42 73 84 22 112 196 7 57 79 155 158 76 84 22 75 121 85 191 100 97 15 37 102 69 38 64 195 145 23 58 15 146 107 193 140 84 144 86 14 150 26 60 46 166 80 87 139 195 126 45 37 27 102 62 32 175 39 124 23 93 188 59 186 163 187 47 168 92 143 147 157 54 51 61 199 43 103 63 184 16 188 197 60 58 86 178 53 171 125 39 144 146 73 124 4 93 32 99 158 132 80 91 96 75 174 55 196 61 188 116 41 114 183 28 77 54 36 163 187 147 179 65 63 190 43 186 59 189 62 193 185 79 53 171 102 146 84 198 14 58 137 8 166 175 32 113 18 115 196 42 200 132 121 19 112 133 172 34 63 48 24 116 183 111 167 21 162 90 181 147 105 106 101 33 123 153 184 128 168 61 59 64 91 149 122 53 8 120 113 124 119 25 132 131 193 121 144 68 185 108 175 107 57 65 186 17 12 114 82 3 66 159 167 197 50 101 176 94 54 134 41 165 157 194 180 77 103 74 61 66 188 36 116 3 65 183 72 180 77 16 136 177 82 159 28 95 48 50 187 21 44 54 176 67 91 156 102 68 175 131 144 15 18 146 119 20 200 46 112 139 75 80 86 137 68 122 171 55 78 175 96 75 71 93 118 195 115 67 79 45 158 15 120 155 193 87 146 81 25 64 23 69 91 108 125 131 81 75 85 174 145 89 27 200 35 156 1 98 86 23 191 127 31 57 70 165 123 163 153 12 43 168 3 114 82 148 190 129 74 176 47 110 181 41 30 71 193 79 171 68 124 98 120 73 75 93 151 108 89 155 19 96 22 119 7 125 85 127 40 55 140 31 72 109 169 24 116 17 114 182 190 141 186 192 28 104 13 66 165 162 36 159 77 110 129 130 181 73 91 80 27 160 4 20 100 56 193 60 38 18 25 172 76 14 55 52 149 96 78 71 195 127 5 112 97 93 74 88 104 197 111 130 95 11 138 123 77 159 65 179 94 165 70 141 16 153 136 83 49 75 91 79 27 171 68 158 87 81 22 119 71 166 57 60 35 160 69 175 26 193 45 127 67 126 89 20 5 31 198 6 76 37 178 175 120 122 57 52 34 4 156 98 115 133 131 171 149 85 38 174 39 73 99 14 140 35 135 172 9 7 6 77 24 116 17 72 190 110 36 173 143 94 65 29 61 154 2 161 90 66 159 28 128 117 11 50 138 74 30 78 156 80 53 164 68 131 144 107 73 195 55 175 1 126 7 149 171 81 91 52 124 40 9 79 80 37 158 40 75 108 198 25 62 42 7 86 57 102 122 145 175 71 1 35 164 68 118 56 144 200 139 20 112 135 172 163 80 91 144 100 118 45 78 139 112 149 98 113 87 195 124 85 73 119 19 79 99 58 56 52 146 81 4 60 137 67 126 145 97 34 134 81 86 27 120 39 131 40 132 25 69 96 26 127 108 75 68 135 98 80 115 149 78 22 4 45 172 82 161 186 109 153 43 159 114 101 104 70 29 197 192 116 148 65 152 184 13 154 92 110 130 11 147 66 176 83 17 13 153 88 111 90 117 95 11 33 147 28 109 199 48 74 167 182 154 101 84 149 58 86 178 171 62 175 113 26 135 96 198 39 19 57 144 37 118 32 56 119 4 98 25 200 150 55 85 156 80 185 155 102 56 158 39 76 15 69 38 150 175 118 137 71 35 120 57 55 135 86 58 84 120 81 112 37 60 46 185 193 38 125 118 175 149 99 108 126 133 102 79 56 144 67 69 31 109 87 80 149 58 118 25 75 126 115 68 178 37 200 32 40 164 56 42 193 107 1 39 113 145 89 172 6 34 93 88 36 116 12 47 165 168 29 83 159 154 74 148 92 176 180 33 110 194 167 17 114 173 16 11 89 37 27 102 32 42 18 99 71 151 19 55 75 98 131 69 45 31 38 195 87 20 135 115 90 163 116 13 173 28 110 190 77 129 117 130 10 179 92 134 194 21 63 83 157 94 152 199 91 126 14 75 135 107 80 102 67 160 158 144 23 64 155 4 198 40 9 73 69 193 185 149 164 42 78 60 98 19 1 165 92 161 109 163 187 88 186 141 51 117 197 59 173 192 82 29 143 116 41 30 111 148 129 90 194 152 170 93 68 99 71 60 45 150 145 98 25 87 122 178 185 7 144 4 22 73 58 112 94 48 163 65 173 182 154 77 21 117 11 147 74 189 43 114 47 177 192 104 90 95 123 141 169 17 168 114 179 21 33 165 167 177 41 103 83 199 129 182 188 74 66 157 152 54 176 96 171 164 68 56 52 18 73 84 81 124 22 71 60 126 150 20 97 38 149 158 196 115 97 185 149 37 178 122 108 118 32 131 1 31 140 73 34 45 25 80 133 57 96 98 80 171 164 158 120 76 99 81 71 37 91 151 144 172 140 150 160 121 84 53 139 89 69 31 133 93 99 80 86 178 122 118 125 52 193 32 174 46 113 98 93 89 150 102 76 100 124 4 60 55 5 38 196 100 80 185 149 27 8 113 131 15 73 99 22 4 200 45 102 172 57 164 38 39 1 112 9 101 165 10 188 109 141 163 187 12 168 82 65 148 180 47 167 2 162 169 192 30 179 11 44 83 170 63 102 91 86 79 53 171 155 67 113 39 137 158 196 166 120 42 89 58 5 119 85 62 52 146 99 121 100 57 103 161 188 186 184 153 159 167 189 2 168 13 29 104 142 33 65 197 117 148 44 95 181 59 49 104 134 188 186 141 184 41 187 168 114 82 148 192 194 154 74 3 190 161 105 163 72 103 94 170 51 105 165 48 161 116 159 104 21 129 63 44 169 106 142 190 181 143 179 157 173 188 199 176 106 36 163 169 184 41 159 29 197 111 16 179 162 105 138 148 50 165 63 173 109 107 91 58 56 125 158 87 191 133 9 38 122 164 175 135 4 35 14 7 185 78 18 146 151 26 64 126 55 20 112 198 172 108 86 178 79 164 37 25 195 144 120 198 26 56 19 132 69 193 115 45 172 97 155 8 81 71 166 139 174 64 31 41 109 10 47 116 12 128 51 167 180 179 33 123 101 142 92 143 199 154 3 72 82 141 17 168 114 173 183 148 189 11 181 106 83 152 49 86 110 165 186 36 163 169 43 88 168 33 138 147 13 167 189 184 134 72 90 188 82 77 44 54 70 111 41 92 114 162 188 129 187 170 152 83 142 74 157 16 13 138 186 106 63 184 28 21 50 30 192 112 193 80 86 27 137 174 67 5 79 198 132 127 42 131 100 73 107 56 135 62 7 93 113 156 80 149 171 102 62 39 133 84 87 198 1 53 64 55 172 122 100 42 14 160 99 124 137 45 19 145 7 114 48 104 136 16 61 72 181 128 82 88 138 109 129 70 192 3 153 65 95 44 111 28 21 11 94 54 115 185 37 27 108 68 62 87 120 76 81 22 25 151 139 191 140 9 89 96 18 116 48 188 109 24 157 61 41 181 128 66 88 63 152 189 168 90 105 72 77 10 13 47 82 173 92 142 28 180 2 21 117 50 33 136 164 117 17 47 92 16 179 2 103 90 194 189 192 94 143 170 162 83 116 129 184 77 138 152 51 49 118 193 156 80 86 155 68 196 145 40 4 97 79 5 99 87 149 174 34 137 166 131 15 160 84 121 85 119 80 178 102 52 160 124 84 185 6 22 67 174 8 121 133 5 75 64 15 150 71 151 145 20 120 185 86 171 108 102 68 200 193 126 64 160 32 150 6 115 98 81 56 191 76 124 71 139 85 195 135 121 156 185 37 32 15 146 22 119 4 98 151 57 62 126 53 139 40 102 35 118 64 135 133 122 156 146 23 99 196 46 14 56 53 175 164 20 68 39 195 126 97 40 34 64 79 27 155 113 76 131 15 42 107 166 151 9 93 36 123 165 194 50 70 95 11 153 30 24 17 49 47 54 2 189 147 199 3 188 197 186 109 41 29 129 130 128 74 136 63 156 124 193 80 125 32 146 99 23 5 60 113 120 191 6 58 64 119 71 37 78 96 137 125 37 86 56 4 133 69 178 132 53 172 45 60 151 40 198 55 35 107 99 124 71 137 127 23 126 91 58 86 122 155 87 120 146 78 200 121 19 80 20 137 75 96 107 18 156 46 135 127 37 178 32 52 131 160 81 4 25 191 125 38 71 15 8 42 75 46 174 73 14 69 112 172 9 34 128 48 134 161 109 116 187 114 183 16 179 189 130 181 142 123 138 2 136 77 152 63 129 165 184 41 153 114 148 111 177 16 180 44 29 123 54 173 72 92 70 199 105 90 117 95 157 130 186 169 24 3 154 189 21 136 72 82 74 190 11 47 13 173 54 181 43 123 90 128 50 138 30 176 131 193 53 76 78 22 69 97 118 178 122 140 81 34 164 8 100 127 67 31 6 42 146 200 195 26 64 46 55 89 112 132 185 149 53 171 108 125 18 81 60 25 139 191 178 64 52 9 62 22 40 164 35 112 133 86 53 56 125 8 52 113 76 107 119 195 97 156 98 121 62 140 26 175 9 134 153 11 17 182 165 197 138 173 24 28 104 128 29 2 167 152 183 3 162 154 186 13 65 142 110 90 50 33 157 80 135 91 171 164 107 84 81 45 5 35 112 120 15 151 85 76 79 178 121 126 89 136 165 36 187 3 114 173 190 130 128 66 74 152 123 154 116 28 49 153 16 169 137 156 185 53 155 102 118 62 166 175 200 151 112 113 14 124 80 146 35 125 34 85 67 126 145 172 138 134 186 153 114 111 142 110 179 21 128 130 117 197 169 77 13 74 51 180 50 106 54 139 80 58 27 164 132 121 108 115 140 31 79 98 15 160 52 26 171 39 195 120 67 14 35 196 34 140 185 58 56 8 175 131 144 18 4 166 98 139 1 195 22 156 71 76 178 115 97 133 141 109 104 184 2 143 188 51 49 33 197 48 176 95 159 148 101 154 13 170 190 36 43 3 92 72 16 28 167 180 147 74 54 178 142 161 109 169 12 183 111 163 187 162 180 16 165 116 184 138 44 13 49 134 143 177 103 128 181 105 192 143 165 161 109 141 24 184 168 92 142 154 180 51 147 179 176 183 189 59 159 167 77 117 105 152 144 91 80 58 178 27 53 164 108 8 158 60 79 67 155 78 140 7 86 26 174 84 98 64 19 46 145 6 93 145 178 79 155 118 18 151 69 39 113 42 119 93 80 144 87 15 137 23 158 166 5 57 172 146 149 58 37 122 62 60 68 107 31 67 172 195 121 131 102 185 174 124 126 80 22 137 46 5 147 123 186 36 47 183 29 182 197 16 167 110 143 168 83 82 141 63 94 54 59 157 170 61 148 10 188 186 141 163 12 43 88 82 109 192 70 161 30 129 24 92 49 177 29 104 197 154 101 103 162 181 106 44 176 149 156 80 200 146 15 185 87 91 100 45 37 178 18 32 64 132 97 84 150 113 86 118 76 73 81 78 22 31 96 23 161 150 149 58 8 175 120 39 99 119 166 98 200 85 14 4 46 96 84 22 93 52 151 125 52 160 71 166 98 137 145 122 171 119 193 175 32 121 107 115 18 39 89 135 196 152 134 161 36 116 41 17 82 111 28 128 157 13 92 47 143 117 109 90 95 136 170 153 165 48 123 134 10 186 138 187 103 82 70 163 129 188 170 173 24 83 167 41 43 3 114 154 180 74 136 63 30 154 134 10 109 141 36 41 88 159 82 104 143 148 197 44 13 94 130 162 177 153 167 77 2 83 136 170 155 91 185 53 164 108 145 171 200 6 122 8 9 85 57 1 137 126 102 118 46 68 158 39 144 160 71 172 156 7 53 113 45 14 193 122 40 67 19 121 22 118 78 5 137 166 149 32 85 178 27 158 76 126 140 69 133 9 23 123 157 184 116 13 3 65 111 90 105 187 147 152 134 59 95 186 197 44 170 129 21 158 91 193 79 27 102 68 32 75 156 107 185 144 4 57 39 155 98 171 85 25 175 60 145 38 96 159 188 141 36 24 13 12 88 103 105 179 177 17 3 182 51 82 28 161 154 106 65 183 72 143 77 66 74 160 91 185 53 32 120 155 6 9 18 127 171 118 113 119 151 26 46 195 200 73 98 75 139 40 1 5 198 38 161 165 10 24 173 142 182 162 92 13 152 33 82 189 43 143 128 103 186 105 12 188 184 41 17 159 148 104 180 77 194 170 149 162 134 161 188 186 36 24 173 182 111 142 72 154 101 48 148 2 179 106 63 41 117 163 177 92 10 148 101 44 169 59 110 188 17 51 90 186 94 11 24 70 106 182 41 153 187 104 142 190 61 79 164 185 37 122 175 139 144 91 35 19 96 98 78 155 1 108 198 42 135 79 195 8 52 87 131 107 166 132 100 34 116 165 30 105 36 101 167 183 43 50 70 189 181 190 161 123 136 51 143 129 153 110 134 169 13 47 88 65 142 72 95 106 74 91 166 156 58 27 102 118 62 52 191 140 164 40 122 151 108 75 174 137 196 150 34 200 45 26 145 6 167 165 134 109 24 17 153 187 88 168 65 182 177 154 16 194 141 103 50 147 63 110 101 179 143 21 95 83 168 36 169 116 88 48 70 30 33 101 104 109 110 143 181 167 54 199 49 59 95 177 180 103 50 147 63 169 163 50 184 12 176 106 41 194 173 168 110 142 44 95 130 24 165 182 72 177 197 28 101 138 105 136 51 27 170 10 186 141 17 13 153 111 117 157 92 161 152 147 104 179 154 43 101 36 199 171 34 60 68 31 20 42 62 4 120 71 32 135 113 175 84 102 132 96 98 75 155 56 8 158 76 160 78 151 139 55 184 172 185 108 125 113 146 73 98 174 100 155 81 79 76 127 87 137 107 19 62 145 173 134 10 161 169 13 153 109 162 44 21 88 182 3 190 179 136 90 16 116 94 92 28 77 129 130 105 106 174 27 118 175 76 144 15 146 99 119 166 45 32 19 172 191 60 108 37 69 112 127 175 86 122 79 171 164 68 62 84 140 5 40 196 46 174 150 67 58 76 193 158 107 78 22 137 75 151 85 195 64 1 133 176 141 169 13 47 88 3 65 183 177 143 148 82 105 130 66 181 44 21 182 95 70 177 10 36 163 169 159 29 148 190 12 199 167 176 180 2 192 168 142 41 179 129 154 28 21 95 66 94 178 149 76 19 52 127 108 45 156 60 198 99 37 144 7 97 145 84 119 42 191 53 125 8 87 131 18 25 132 195 140 135 93 141 179 10 109 36 159 173 177 49 117 12 48 101 189 2 138 128 95 106 28 167 16 143 162 90 105 74 170 199 30 61 180 48 109 17 88 142 177 16 65 194 36 153 116 161 66 143 141 129 47 168 21 101 181 138 181 165 188 184 116 13 168 114 182 130 128 44 103 148 63 29 142 180 17 109 72 105 176 70 182 134 10 161 163 169 184 13 159 173 183 147 189 162 181 12 72 167 94 199 192 2 95 44 83 176 183 165 48 134 188 186 63 33 147 43 61 109 142 159 66 41 128 182 176 190 184 143 189 184 48 10 141 169 24 143 41 161 181 36 129 197 104 186 182 28 106 157 103 199 82 183 111 142 110 117 63 51 59 171 185 193 140 8 97 7 121 160 155 85 172 91 100 164 132 25 120 20 62 137 115 149 86 32 158 107 146 119 64 55 93 10 186 161 104 199 162 148 110 138 183 153 103 192 82 130 123 59 49 147 134 65 170 163 184 187 92 197 111 72 157 61 37 187 24 153 186 92 189 54 33 59 21 167 163 101 136 50 197 16 104 128 192 30 47 111 142 66 157 61 49 188 48 123 50 104 36 101 148 66 161 44 28 21 162 116 183 103 159 181 61 29 141 163 153 111 110 190 95 105 59 58 189 165 123 10 161 116 41 187 43 29 182 197 16 110 179 143 12 183 103 199 109 130 128 194 117 94 61 190 165 48 10 141 13 43 3 173 183 104 177 72 36 77 188 90 136 51 163 70 130 105 61 191 193 37 178 8 32 120 15 42 107 18 124 166 132 174 20 52 57 31 115 127 1 69 9 23 192 186 187 12 114 82 92 29 148 104 182 177 72 28 101 21 117 94 51 111 142 193 26 112 191 62 195 25 91 39 71 158 131 46 5 38 37 185 18 118 124 56 156 58 86 53 108 68 175 87 120 15 42 73 99 4 75 151 64 35 48 194 123 169 43 88 65 29 104 16 167 180 90 189 161 199 47 92 3 12 17 117 195 193 80 58 122 164 108 68 160 146 78 139 23 120 178 133 73 175 37 131 9 19 89 140 57 196 122 53 102 118 62 175 15 166 31 9 37 6 99 151 56 139 46 1 96 60 197 48 123 134 141 184 187 82 65 92 106 148 147 199 29 17 30 189 186 74 169 154 21 103 138 157 59 198 91 37 178 79 164 108 125 62 113 18 84 45 26 112 35 107 160 53 1 75 199 123 186 109 184 43 168 29 182 197 177 189 129 194 95 83 170 54 105 90 179 30 59 200 149 155 52 87 120 39 160 137 27 79 131 100 25 55 23 126 84 166 150 62 67 1 69 35

### jimiolaniyan commented Apr 25, 2018 • edited Edited 1 time jimiolaniyan edited Apr 25, 2018

 One liner for `load_graph()`: ``````def load_graph(): return {int(line.rstrip().split()[0]): [int(i) for i in line.rstrip().split()[1:]] for line in open(".kargerMinCut.txt")} ``````