Teaching Kids Programming – Three Graph Algorithms: Does Every Vertex Have at least One Edge in Graph?

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given n people represented as an integer from 0 to n – 1, and a list of friends tuples, where person friends[i][0] and person friends[i][1] are friends. Return whether everyone has at least one friend.

Constraints
m ≤ 100,000 where m is the length of friends
Example 1
Input
n = 3

1 2 3 4

friends = [     [0, 1],     [1, 2] ]

friends = [
    [0, 1],
    [1, 2]
]

Output
True
Explanation
Person 0 is friends with 1
Person 1 is friends with 0 and 2
Person 2 is friends with 1.

Example 2
Input
n = 3

1 2 3

friends = [     [0, 1] ]

friends = [
    [0, 1]
]

Output
False
Explanation
Person 2 is not friends with anyone.

Hints:
child count = 1;
A person has a friend if it’s present in the given list.

Check Each Vertex in Graph for Length of Connections: Bruteforce Algorithm

We can iterate all vertex and check the length of connections (number of edges) to it. In order to this, we can build the graph using Adjacent Linked List.

1
2
3
4
5
6
7

class Solution:
    def atLeastOneEdgeEveryVertex(self, n, friends):
        G = defaultdict(list[int])
        for a, b in friends:
            G[a].append(b)
            G[b].append(a)
        return all(len(G[i]) > 0 for i in range(n))

class Solution:
    def atLeastOneEdgeEveryVertex(self, n, friends):
        G = defaultdict(list[int])
        for a, b in friends:
            G[a].append(b)
            G[b].append(a)
        return all(len(G[i]) > 0 for i in range(n))

Time complexity and space complexity is O(N) as we need to iterate over all vertices and use a adjacent linked list to store the graph.

Disjoint Set (Union Find Algorithm) to Check the Connections of Edges in Graph

We can use a disjoint set (full source code at github) to process the Graph. Then, we merge the groups a and b if there is an edge between a and b. Lastly, we can count the group ID and their appearance – to check if the min appearance time is greater than 1. If it is one, it means we have a vertex that doesn’t connect to any other vertices.

1
2
3
4
5
6
7

class Solution:
    def atLeastOneEdgeEveryVertex(self, n, friends):
        uf = UnionFind(n)
        for a, b in friends:
            uf.unite(a, b)
        g = Counter([uf.findset(x) for x in range(n)])
        return min(g.values()) > 1

class Solution:
    def atLeastOneEdgeEveryVertex(self, n, friends):
        uf = UnionFind(n)
        for a, b in friends:
            uf.unite(a, b)
        g = Counter([uf.findset(x) for x in range(n)])
        return min(g.values()) > 1

Roughly O(N) time considering the merging/findset operation is nearly constant if we compress the path. And the space complexity is O(N) as well as we are using a disjoint set and also the Counter object.

Check the Connections of Edges in Graph using a Boolean Array

If there is an edge between a and b, both vertices have at least 1 connection – which can be marked. Then we can just use a boolean array to mark the vertices by the edges. The answer is to count if there is an unmark vertex.

1
2
3
4
5
6
7

class atLeastOneEdgeEveryVertex:
    def solve(self, n, friends):
        data = [False] * n
        for a, b in friends:
            data[a] = True
            data[b] = True
        return data.count(False) == 0

class atLeastOneEdgeEveryVertex:
    def solve(self, n, friends):
        data = [False] * n
        for a, b in friends:
            data[a] = True
            data[b] = True
        return data.count(False) == 0

Time and space complexity is O(N).

–EOF (The Ultimate Computing & Technology Blog) —