Find a chain that fill range without gaps

Question

Given a range f.e. :

range : 1 4

there are 3 lists of pairs that 'fill' this range w/o gaps. Call it a 'chain'

chain1: 1 2, 2 3, 3 4
chain2: 1 2, 2 4
chain3: 1 3, 3 4

the following lists of pairs fail to fill the range, so it is not a chain :

1 2       <= missing 2 3, 3 4 OR 2 4
1 3       <= missing 3 4
1 2, 3 4  <= missing 2 3
1 2, 2 3  <= missing 3 4
2 3, 3 4  <= missing 1 2

Now the question is given a random list of pairs and a range how can I find is there a combination of pairs that makes a CHAIN.

Pairs do not repeat, are always (lower-value, higher-value) and never overlap i.e. this is never an input [ 1 3, 2 4 ]

In addition I can pre-filter only the pairs that are within the range, so f.e. you dont have to worry about pairs like : 4 6, 7 9, 0 1 ...

---

update ... this is also valid input

chain: 1 2, 1 3, 3 4
chain: 1 2, 1 3, 1 4
chain: 1 2, 2 4, 3 4

i.e a pair can subsume another .... this breaks the sort-and-loop idea

Answer 1

implemented the Union-Find algo from here in python ..

q=QFUF(10)

In [131]: q.is_cycle([(0,1),(1,3),(2,3),(0,3)])
Out[131]: True

In [132]: q.is_cycle([0,1,4,3,1])
Out[132]: True

only cares about first two elements of the tuple

In [134]: q.is_cycle([(0,1,0.3),(1,3,0.7),(2,3,0.4),(0,3,0.2)])
Out[134]: True

here

import numpy as np

class QFUF:

    """ Detect cycles using Union-Find algorithm """

    def __init__(self, n):
        self.n = n
        self.reset()

    def reset(self): self.ids = np.arange(self.n)

    def find(self, a): return self.ids[a]

    def union(self, a, b):

        #assign cause can be updated in  the for loop
        aid = self.ids[a]
        bid = self.ids[b]

        if aid == bid : return

        for x in range(self.n) :
            if self.ids[x] == aid : self.ids[x] = bid

    #given next ~link/pair check if it forms a cycle    
    def step(self, a, b):
        # print(f'{a} => {b}')
        if self.find(a) == self.find(b) : return True
        self.union(a, b)
        return False

    def is_cycle(self, seq):
        self.reset()
        #if not seq of pairs, make them
        if not isinstance(seq[0], tuple) :
            seq = zip(seq[:-1], seq[1:]) 

        for tpl in seq :
            a,b = tpl[0], tpl[1]
            if self.step(a, b) : return True
        return False