[Question]
  [
In graph theory, a [Cactus](https://en.wikipedia.org/wiki/Cactus_graph) is a connected graph such that any distinct two simple cycles in the graph share at most one vertex.
Here is a Cactus with 3 simple cycles outlined with dashed lines.
[![Cactus Graph](https://i.stack.imgur.com/40a39.png)](https://i.stack.imgur.com/40a39.png)
The following graph is similar to the one pictured above but is not a Cactus because the two vertices labeled in red are shared by two simple cycles.
[![Not Cactus Graph](https://i.stack.imgur.com/lg4hN.png)](https://i.stack.imgur.com/lg4hN.png)
Things can get a little bit trickier, for example the following graph:
[![Also not a Cactus graph](https://i.stack.imgur.com/xLdUq.png)](https://i.stack.imgur.com/xLdUq.png)
Might look like a Cactus but it is not. This can be shown by highlighting the following cycle:
[![Highlighted cycle](https://i.stack.imgur.com/3ZJnW.png)](https://i.stack.imgur.com/3ZJnW.png)
This cycle shares more than one point with a lot of the more obvious cycles in the graph.
### Definitions
* A connected graph is a graph such that there exists at least one path between any two vertices.
* A simple cycle is a path on a graph that starts and ends at the same vertex and visits no vertex more than once.
* A simple graph is an undirected, unweighted graph such that no vertices are connected two each other by more than one edge and no vertex is connected to itself. A simple graph is the most basic type of graph and is what most people mean when they say graph.
# Task
Take a simple graph as input and decide whether it is a Cactus graph. You should output two distinct values one for True and one for False. You may take input in any format you see fit.
This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'") so you should aim to minimize the byte count of your answers.
[Test Cases](https://gist.github.com/Wheatwizard/5cbaf2b496f40d7be4aade412f25153a)
[Test Cases as Adjacency Matrices](https://gist.github.com/Wheatwizard/d147308c59ca9e38477eccdbddeabf10)
  
[Answer]
# Mathematica, 62 bytes
```
Sort@#==#⋃#&[Join@@FindCycle[#,∞,All]]&&ConnectedGraphQ@#&
```
Checks: `(find all cycles, there are no duplicate edges)` and `(The graph is a connected graph)`
[Answer]
# [Python 2](https://docs.python.org/2/), ~~299~~ 289 bytes
```
j=input()
n=len(j)
Q=range(n*n)
L=N=[[{1<<i%n|1<<i/n}]*j[i/n][i%n]for i in Q]
for _ in Q:N=[[a|b for A,B in zip(N[i/n::n],N[i%n::n])for a in A for b in B if{1}>a&b]for i in Q];L=[L[i]+N[i]for i in Q]
1/all(L[i]*all(A&B|B&C|C&A for A in L[i]for B in L[i]for C in L[i])for i in Q if i%n<i/n)
```
[Try it online!](https://tio.run/##zVVhb9owEP2eX2FlGkpoRJJqtFPWTIK2TJMQW9V9WhZVAUxrltqRbZqy0t/Ozg6EsJKBtn1YhMjL3b2792wHsrm8Y/R4KbGQAoUoMhBclv5WV1Qi/eQ5yIdP7GyHIebtDqtMJVyBX/gMF0@2s3/oromH9o1WsoGwlqqht4KAe0kq8CE6Xjiq@q9fgh2Znd0qUEs6fIHWc@q11STrtXsVZn3yX@1wqXGfhz02duW3nNSa2Wf2v/Xr7/Hr/Znfnfy/8Fvv1Putxnp1h7w5sWHgRzy6EZITegs/caZpLqchodlMWrZBwxRTa2obVyFP6C22aJPaRj8chFH05J@dkdd0oW4ufY6b0wjucQSxeMI4IohQdBUbCt9oHChashgiFeo4XRX8QTJroIhBQGNnoNgK2aokUQUdXT1UEAiTJ//5fdIYVie864dRPyLxEbC3JvtukqaWSjUV6DS6i27jfHHeKHp2VFl/xelWH87XD/amHcxGIE55tZewSsYrdDm4QB8@9XsG4GtyP0sTiZGQYyjXvNUikvuMcYmYcJCYC1V8J2UmAtcVMhl9Zw@YT1KWt0bs3k1cv@212yfHJ@7pm7d@2z81uINy2BgmWhnJsNoUnN8UU3R0MmYZbBKUmdy0DZaOi6ye1loXlthBJd/Itzrk0CGHDnrpx1On2DX93xfo85K3ck4ktjjOuAUVNjpC5jcKFBCfMqHEbdj4McMjice/NJF8HpSHUZ09q3IA7TLDsZilEvSp98goakc4k@gr5uyCPBBBGL3knPHgJUefcR2GTVtHw1LRhpHBUGmZnzvX12YxGwPzRb7X@djfGDI3EFZsOJPolkkIFoPs5U8 "Python 2 – Try It Online") (simulates STDIN to run all test cases at once)
*-10 bytes thanks to @ovs*
Takes input as an adjacency matrix from STDIN.
Outputs by the presence of an error in accordance with [a default output method](https://codegolf.meta.stackexchange.com/a/11908/68261). An IndexError represents non-cactus, and no error represents cactus.
## Theory
A simple cycle can be thought of as two disjoint simple paths between a pair of vertices. Similarly, our conjoined cycles correspond to three distinct simple paths being present between a pair of vertices (better explanation near the bottom of the ungolfed code).
To detect these conjoined cycles, we:
* find all paths between all pairs of vertices, keeping track of the edges using Python sets.
* for each pair of vertices, if three paths are pairwise disjoint, then a conjoined cycle is present.
The first bullet has the side-benefit of making the connectedness easy to test: if a path exists between every pair of distinct vertices, then the graph is connected.
## Potential improvements
If input could be taken via STDIN as `n` followed by `n*n` rows of boolean values, 13 bytes could be saved, but it doesn't feel right.
A lot of generator for-loop code is repeated, so surely there's a better way. I tried `itertools.product`, but that ended up with a net cost of +9 bytes. I might have to go with exec/string-replacement abuse like in [Baba](https://codegolf.stackexchange.com/a/206476/68261), which could especially help with `for i in Q` being used four times.
## Ungolfed Code
Python 2 has two main benefits over Python 3 here:
* `input()` automatically parses the input
* Division is floor division by default.
```
j = input()
n = len(j)
Q = range(n * n)
# Replace each 0 in the adjacency matrix with []
#   and each edge with a label such that the element of N representing the edge m→n has the
#   same label as the element of N representing the edge n→m
L = N = [
    # Each edge label is a 2-hot integer (easiest way to ensure ensure equality in both directions since the graph is undirected)
    # Each path's edge sequence is stored as a set of edge labels
    # N[i] is a list of paths from vertex i % n to vertex i / n
    # N[i] starts out as all possible paths of length 1, i.e. edges
    # L[i] starts as the same
    [{1 << i%n | 1 << i/n}]
    * j[i / n][i % n]
    for i in Q
]
# Repeat this n**2 times:
# (In reality, only about log_2(n) times is needed, but there isn't a big performance loss)
for _ in Q:
    # Update N from the list of all possible paths of length k to the list of all possible paths of length k+1
    N = [
        [
            # The union of two paths is possible
            a | b
            # ... for every paths list in N
            for A, B in zip(N[i / n :: n], N[i % n :: n])
            # ... and for every pair of paths in each of these paths lists
            for a in A
            for b in B
            # Limit the search to be through disjoint paths only
            # equivalent to `{1}>a&b == not a&b` because a,b contain only tuples, not integers
            if {1} > a & b
        ]
        for i in Q
    ]
    # Update L from being list of all possible paths of length at most k to the list of all possible paths of length at most k+1
    # (It really seems like these two generator for-loops can be merged into one for loop, but I couldn't get it to work
    #  I might be able to store L and N in the same list, but that's super slow performance; hard to test)
    L = [L[i] + N[i] for i in Q]
# Raises a ZeroDivisionError iff the result of the `all` call is False
1/all(
    # L[i] is falsey ←→ L[i] is an empty list ←→
    # no path exists between vertices i%n and i/n ←→ graph is not connected ←→ not cactus
    L[i]
    * all(
        # `A & B | B & C | C & A` is falsey
        # → A,B,C are three disjoint simple paths between vertices i%n and i/n
        # → AB' and CB' are two cycles that share an edge
        # → The graph is non-cactus
        A & B | B & C | C & A
        # using itertools.product is net +9 bytes last I checked
        for A in L[i]
        for B in L[i]
        for C in L[i]
    )
    for i in Q
    # L is symmetric, and we don't want to check the main diagonal
    if i % n < i / n
)
```
## Super-ungolfed code
```
def dot(r1, r2):
    return [
        path1 | path2
        for paths1, paths2 in zip(r1, r2)
        for path1 in paths1
        for path2 in paths2
        # simple paths, so exclude those that share edges
        if len(path1 & path2) == 0
    ]
def mul(paths1, paths2):
    return [[dot(row, col) for row in zip(*paths2)] for col in paths1]
def f(adj):
    n = len(adj)
    paths_length_1 = [
        [
            [{(min(x, y), max(x, y))}] if entry == 1 else []
            for x, entry in enumerate(row)
        ]
        for y, row in enumerate(adj)
    ]
    all_paths = paths_length_1
    paths_length_n = paths_length_1
    for _ in range(n):
        paths_length_n = mul(paths_length_1, paths_length_n)
        for y in range(n):
            for x in range(n):
                all_paths[y][x].extend(paths_length_n[y][x])
    for x, row in enumerate(all_paths):
        for y, paths in enumerate(row):
            # The graph is non-cactus if it is not conneted
            if x != y and len(paths) == 0:
                return False
            # The graph is non-cactus if there exist three piecewise disjoint simple paths A,B,C
            # between two nodes because A+B' forms one cycle and C+B' forms the other cycle
            for A, B, C in itertools.combinations(paths, 3):
                if len(A & B) == 0 and len(B & C) == 0 and len(A & C) == 0:
                    return False
    return True
```
]