diff options
Diffstat (limited to 'findloop.c')
| -rw-r--r-- | findloop.c | 31 |
1 files changed, 30 insertions, 1 deletions
@@ -14,7 +14,7 @@ #include "puzzles.h" struct findloopstate { - int parent, child, sibling; + int parent, child, sibling, component_root; bool visited; int index, minindex, maxindex; int minreachable, maxreachable; @@ -57,6 +57,33 @@ bool findloop_is_loop_edge(struct findloopstate *pv, int u, int v) return !(pv[u].bridge == v || pv[v].bridge == u); } +static bool findloop_is_bridge_oneway( + struct findloopstate *pv, int u, int v, int *u_vertices, int *v_vertices) +{ + int r, total, below; + + if (pv[u].bridge != v) + return false; + + r = pv[u].component_root; + total = pv[r].maxindex - pv[r].minindex + 1; + below = pv[u].maxindex - pv[u].minindex + 1; + + if (u_vertices) + *u_vertices = below; + if (v_vertices) + *v_vertices = total - below; + + return true; +} + +bool findloop_is_bridge( + struct findloopstate *pv, int u, int v, int *u_vertices, int *v_vertices) +{ + return (findloop_is_bridge_oneway(pv, u, v, u_vertices, v_vertices) || + findloop_is_bridge_oneway(pv, v, u, v_vertices, u_vertices)); +} + bool findloop_run(struct findloopstate *pv, int nvertices, neighbour_fn_t neighbour, void *ctx) { @@ -94,6 +121,7 @@ bool findloop_run(struct findloopstate *pv, int nvertices, */ pv[v].sibling = pv[root].child; pv[root].child = v; + pv[v].component_root = v; debug(("%d is new child of root\n", v)); u = v; @@ -116,6 +144,7 @@ bool findloop_run(struct findloopstate *pv, int nvertices, pv[w].child = -1; pv[w].sibling = pv[u].child; pv[w].parent = u; + pv[w].component_root = pv[u].component_root; pv[u].child = w; } |