aboutsummaryrefslogtreecommitdiff
path: root/divide_nodes_max_groups.py
blob: e6cf7bcc489b1f469d0df3610fed35f98c7bb243 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
# 2493. Divide Nodes Into the Maximum Number of Groups
from collections import deque

"""
you are given a positive integer 'n' representing the number of nodes in an
undirected graph. the nodes are labeled from 1 to 'n'. you are also given a
2d integer array 'edges', where 'edges[i] = [a_i, b_i]' indicates that there
is a bidirectional edge between nodes 'a_i' and 'b_i'. divide the nodes of
the graph into 'm' groups such that each node in the graph belongs to exactly
one group, and for every pair of nodes in the graph that are connected by an
edge '[a_i, b_i]', then '|y - x| = 1'. return the maximum number of groups
into which you can divide the nodes. return -1 if it is impossible.
"""


class Solution(object):
    def magnificentSets(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: int
        """
        graph = [[] for _ in range(n)]
        for u, v in edges:
            graph[u - 1].append(v - 1)
            graph[v - 1].append(u - 1)
        vis, group = [0] * n, []
        for i in range(n):
            if not vis[i]:
                vis[i] = True
                stack = [i]
                group.append([i])
                while stack:
                    u = stack.pop()
                    for v in graph[u]:
                        if not vis[v]:
                            vis[v] = vis[u] + 1
                            stack.append(v)
                            group[-1].append(v)
                        elif vis[u] & 1 == vis[v] & 1:
                            return -1

        def bfs(x):
            res, vis, q = 0, {x}, deque([x])
            while q:
                res += 1
                for _ in range(len(q)):
                    u = q.popleft()
                    for v in graph[u]:
                        if v not in vis:
                            vis.add(v)
                            q.append(v)
            return res

        ans = 0
        for g in group:
            ans += max(bfs(x) for x in g)
        return ans


if __name__ == "__main__":
    obj = Solution()
    print(
        obj.magnificentSets(n=6, edges=[[1, 2], [1, 4], [1, 5], [2, 6], [2, 3], [4, 6]])
    )
    print(obj.magnificentSets(n=3, edges=[[1, 2], [2, 3], [3, 1]]))