| 196 | } |
| 197 | |
| 198 | forceinline int |
| 199 | OfflineMin::find_pc(int x){ |
| 200 | int path_length = 0; |
| 201 | while (sequence[x].parent != x) { |
| 202 | vertices[path_length++] = x; |
| 203 | x = sequence[x].parent; |
| 204 | } |
| 205 | // x is now the root of the tree |
| 206 | // Compress path up to the root |
| 207 | for (int i=0; i < path_length-1; i++) { |
| 208 | sequence[vertices[i]].parent = x; |
| 209 | } |
| 210 | // return the set x belongs to |
| 211 | return sequence[x].name; |
| 212 | } |
| 213 | |
| 214 | forceinline void |
| 215 | OfflineMin::unite(int a, int b, int c){ |