Problem statement

https://binarysearch.com/problems/Short-Circuit/

Solution 1

The idea is that we need to construc Eulerian cycle: it is possible to construct it if and only if

  1. For each node indegree is equal to outdegree
  2. If graph has only one connected component.

Complexity

It is O(n) for time and O(26) for space.

Code

class Solution:
    def solve(self, words):
        def kosaraju(g, n):
            vis, l, comps = [False]*n, [0]*n, [0]*n
            global time
            time, transp = n, [[]] * n

            def visit(u):
                global time
                if vis[u]: return
                vis[u] = True
                for v in g[u]:
                    visit(v)
                    transp[v] = transp[v] + [u]
                time -= 1
                l[time] = u

            def assign(u, root):
                if not vis[u]: return
                vis[u] = False
                comps[u] = root
                for v in transp[u]:
                    assign(v, root)

            for u in range(n): visit(u)
            for u in l: assign(u, u)
            return comps

        letters = set(w[0] for w in words) | set(w[-1] for w in words)
        d = {l:i for i, l in enumerate(letters)}

        G = defaultdict(set)
        G_bal = Counter()
        for w in words:
            G[d[w[0]]].add(d[w[-1]])
            G_bal[w[0]] += 1
            G_bal[w[-1]] -= 1

        if sum(abs(i) for i in G_bal.values()) != 0: return False

        out = kosaraju(G, len(G))
        return out == [0] * len(d)

Solution 2

In fact to check strong connectivity we can use Leetcode 332. Reconstruct Itinerary and Hierholzer’s algorithm, which also can return path as well and which will be shorter.

Complexity

Still O(n).

Code

# not mine code
class Solution:
    def solve(self, words):
        adj = [[] for i in range(128)]
        out, visited, path = [0] * 128, [0] * 128, []
        for w in words:
            s, e = ord(w[0]) - ord("a"), ord(w[-1]) - ord("a")
            adj[s].append(e)
            out[s] += 1
            out[e] -= 1
            visited[s] = visited[e] = 1

        def dfs(start):
            while len(adj[start]) > 0:
                node = adj[start].pop()
                dfs(node)
            path.append(start)
            visited[start] = 0

        dfs(ord(words[0][0]) - ord("a"))
        return path[0] == path[-1] and sum(visited) == 0 and all(out) == 0