Detect that a graph is a flower

user_15601029 0
Viewed 109

A flower is an undirected graph with 2n vertices, having exactly one cycle of length n, and where each node in the cycle is connected to exactly one node of degree 1.

Example:

Sun

Detect that it is a flower with O(n) time complexity.

My attempt:

Use DFS to detect the cycle and store the start and end points. Then backtrace on that cycle.

What I don't have figured out yet is this: while backtracing I need a function which can decide a node is valid. Can someone help me out with this?

Also DFS is V + E, so how can I make it O(V)?

bool dfs(v, prev):
    vis[v] = true
    for u in adj[v]:
        if prev == u:
            continue
        if vis[u]:
            start = u
            end = v
            return true
        parent[u] = v
        if dfs(u, parent[u]):
            return true
    return false

while start != end:
    # check that start is valid here 
    start = parent[start]
graph algorithm
1 Answers

You can do a first iteration over V to check that half of the nodes is of degree 1 and the other half of the nodes is of degree 3. If this is not true, bail out. This check should not require you to visit any edges. The data structure should be able to tell you what a node's degree is in constant time.

Only then do the cycle check. Make sure to start in a node of degree 3. No recursion/backtracking is needed, because you can choose greedily a next node that also has degree 3. Require that the size of the found cycle is exactly n/2. This step will not require more edge visits than n (because of the degree check).

If, and only when, this is true, then it is a flower.

user_54598390
Related