Problem statement

https://binarysearch.com/problems/Logically-Consistent-Book/

Solution

Actually, this problem is about bipartite graph: create edges x - (y + 1) and then check if we can color it with two colors: if we have weight 1, nodes should be in different parts, if it is equal to 0, they should be in the same part.

Complexity

It is O(E + n) for time and space.

Code

class Solution:
    def solve(self, lists):
        G = defaultdict(list)
        for x, y, i in lists:
            G[x] += [(y + 1, i)]
            G[y + 1] += [(x, i)]

        def dfs(start):
            if self.loop: return
            for neib, col in G[start]:
                if dist[neib] >= 0 and dist[neib] ^ col != dist[start]:
                    self.loop = True
                elif dist[neib] < 0:
                    dist[neib] = dist[start]^col
                    dfs(neib)
            
        n = len(G) 
        self.loop, dist = False, defaultdict(lambda: -1)

        for i in G:
            if self.loop: return False
            if dist[i] == -1:
                dist[i] = 0
                dfs(i)
                
        return True