Number of connected components of the given graph

Compute the number of connected components of a given graph. A graph is given as a list of edges, each edge is represented as a tuple contains two node labels. Nodes are labeled with numbers from 0 ... n-1 where n is the number of vertices in a graph.


In [4]:
# Node is represented by a list tuples (parent, length).
# Length is only used in the node that represents a connected component.

def find(i, nodes):
    """
    Find and return the representative of the connected component
    that contains the node i.
    """
    if nodes[i][0] != i:
        # Find the reprentative for the connected component
        # containing node i and point with the parent of the node i
        # to it.
        nodes[i][0] = find(nodes[i][0], nodes)
    return nodes[i][0]

def union(i, j, nodes):
    """
    Merge the connected component that contain nodes labeled i 
    and j. If the nodes belong to the same connected component do
    nothing.
    Returns True if merge succeeds, False otherwise.
    """
    # Find the representatives for the given nodes.
    ri, rj = find(i, nodes), find(j, nodes)
    if ri != rj:
        # Order them according to the sizes of their 
        # connected components.
        ri, rj = sorted([ri, rj], key=lambda e: nodes[e][1])
        # Point the parent from the representative of the smaller connected 
        # component to the representative of the bigger 
        # connected component. 
        # modify the size part of the representative of the new connected component.
        nodes[ri][0] = rj
        nodes[rj][1] += nodes[ri][1]
        return True
    return False
      
def init_nodes(n):
    """
    Create and return the list of n nodes.
    """
    return [[i, 1] for i in range(n)]

In [6]:
init_nodes(5)


Out[6]:
[[0, 1], [1, 1], [2, 1], [3, 1], [4, 1]]

In [7]:
def components(n, edges):
    """
    Return the number of connected components for a graph on 
    n vertices with the given edges.
    """
    components = n
    nodes = init_nodes(n)
    for n1, n2 in edges:
        if union(n1, n2, nodes):
            components -= 1
    return components

In [8]:
grafi = [[[10, 5],
  [38, 65],
  [79, 45],
  [89, 21],
  [49, 5],
  [82, 31],
  [33, 73],
  [39, 80],
  [74, 87],
  [6, 14],
  [56, 15],
  [73, 10],
  [54, 16],
  [51, 47],
  [39, 56],
  [98, 95],
  [0, 21],
  [67, 86],
  [46, 68],
  [59, 91],
  [32, 67],
  [78, 32],
  [44, 1],
  [92, 5],
  [85, 65],
  [36, 47],
  [50, 61],
  [94, 81],
  [92, 55],
  [86, 89],
  [2, 81],
  [96, 76],
  [93, 93],
  [83, 83],
  [60, 58],
  [71, 27],
  [27, 18],
  [60, 11],
  [78, 64],
  [65, 96],
  [39, 9],
  [73, 17],
  [50, 68],
  [53, 70],
  [99, 56],
  [78, 19],
  [32, 85],
  [14, 73],
  [3, 45],
  [28, 34],
  [6, 11],
  [15, 96],
  [78, 14],
  [56, 28],
  [14, 30],
  [13, 72],
  [25, 65],
  [7, 25],
  [54, 70],
  [13, 25],
  [44, 21],
  [11, 8],
  [80, 56],
  [89, 63],
  [8, 2],
  [13, 52],
  [75, 65],
  [60, 73],
  [56, 60],
  [83, 27],
  [37, 33],
  [57, 52],
  [74, 63],
  [68, 56],
  [79, 85],
  [54, 31],
  [63, 55],
  [95, 16],
  [26, 23],
  [85, 91],
  [18, 83],
  [19, 81],
  [69, 8],
  [18, 62],
  [7, 52],
  [50, 6],
  [84, 57],
  [41, 75],
  [13, 63],
  [40, 39],
  [97, 79],
  [86, 7],
  [55, 77],
  [89, 47],
  [31, 33],
  [45, 67],
  [66, 7],
  [1, 83],
  [60, 92],
  [42, 51],
  [85, 7],
  [58, 64],
  [82, 77],
  [16, 61],
  [76, 24],
  [46, 87],
  [53, 89],
  [97, 62],
  [14, 28],
  [23, 54],
  [92, 80],
  [6, 67],
  [36, 18],
  [59, 78],
  [28, 52],
  [6, 18],
  [53, 44],
  [0, 68],
  [90, 12],
  [17, 75],
  [8, 47],
  [97, 10],
  [94, 56],
  [89, 56],
  [10, 30],
  [59, 68],
  [1, 7],
  [33, 78],
  [55, 75],
  [53, 25],
  [36, 66],
  [46, 78],
  [63, 4],
  [54, 1],
  [42, 85],
  [5, 44],
  [20, 63],
  [96, 48],
  [72, 54],
  [57, 75],
  [11, 81],
  [11, 39],
  [41, 71],
  [60, 69],
  [51, 10],
  [33, 61],
  [73, 26],
  [71, 49],
  [33, 69],
  [81, 83],
  [86, 45],
  [79, 30],
  [53, 37],
  [64, 82],
  [10, 95],
  [96, 49],
  [57, 1],
  [86, 66],
  [53, 16],
  [4, 57],
  [80, 84],
  [71, 75],
  [11, 50],
  [38, 27],
  [9, 25],
  [9, 33],
  [79, 40],
  [77, 82],
  [5, 18],
  [24, 28],
  [50, 88],
  [84, 99],
  [27, 17],
  [99, 90],
  [13, 9],
  [15, 27],
  [12, 96],
  [91, 25],
  [80, 2],
  [43, 55],
  [24, 90],
  [40, 33],
  [58, 14],
  [44, 34],
  [3, 45],
  [87, 49],
  [47, 18],
  [21, 53],
  [44, 90],
  [47, 91],
  [93, 46],
  [89, 91],
  [53, 78],
  [41, 8],
  [16, 6],
  [1, 39],
  [56, 31],
  [50, 5],
  [45, 89],
  [13, 92],
  [31, 10],
  [85, 42],
  [12, 38],
  [73, 31],
  [26, 86],
  [60, 31],
  [60, 11],
  [6, 91],
  [29, 35],
  [26, 47],
  [91, 38],
  [0, 25],
  [77, 14],
  [59, 91],
  [13, 36],
  [0, 61],
  [29, 15],
  [78, 8],
  [2, 81],
  [31, 46],
  [28, 11],
  [73, 64],
  [87, 85],
  [85, 75],
  [23, 31],
  [37, 78],
  [43, 43],
  [56, 14],
  [79, 7],
  [45, 88],
  [5, 82],
  [86, 51],
  [5, 91],
  [76, 75],
  [79, 57],
  [13, 2],
  [87, 17],
  [48, 46],
  [18, 95],
  [23, 76],
  [71, 96],
  [76, 4],
  [20, 5],
  [26, 19],
  [54, 61],
  [22, 69],
  [34, 5],
  [69, 83],
  [46, 65],
  [2, 81]],
[[80, 63],
  [33, 52],
  [5, 66],
  [1, 20],
  [59, 17],
  [60, 44],
  [91, 15],
  [77, 51],
  [72, 97],
  [54, 81],
  [49, 41],
  [30, 28],
  [91, 45],
  [0, 14],
  [55, 89],
  [7, 55],
  [53, 95],
  [38, 1],
  [25, 51],
  [75, 83],
  [45, 44],
  [49, 62],
  [84, 85],
  [89, 27],
  [99, 30],
  [86, 2],
  [49, 62],
  [36, 70],
  [94, 28],
  [59, 24],
  [69, 2],
  [24, 0],
  [0, 33],
  [52, 34],
  [69, 32],
  [37, 5],
  [41, 84],
  [99, 16],
  [18, 36],
  [3, 6],
  [96, 1],
  [28, 58],
  [73, 23],
  [32, 67],
  [26, 75],
  [66, 57],
  [95, 56],
  [58, 29],
  [57, 9],
  [30, 43],
  [57, 13],
  [45, 39],
  [71, 13],
  [37, 49],
  [46, 25],
  [79, 86],
  [10, 83],
  [79, 60],
  [54, 95],
  [89, 63],
  [97, 77],
  [35, 88],
  [57, 86],
  [7, 70],
  [15, 21],
  [89, 81],
  [23, 28],
  [97, 73],
  [10, 38],
  [23, 17],
  [0, 27],
  [63, 73],
  [38, 57],
  [21, 46],
  [82, 6],
  [6, 73],
  [29, 83],
  [34, 45],
  [14, 23],
  [58, 25],
  [71, 70],
  [12, 50],
  [39, 3],
  [62, 92],
  [69, 44],
  [57, 17],
  [25, 97],
  [33, 72],
  [83, 25],
  [63, 38],
  [39, 76],
  [70, 17],
  [62, 62],
  [21, 12],
  [6, 73],
  [31, 32],
  [93, 65],
  [60, 48],
  [45, 8],
  [75, 69],
  [22, 83],
  [39, 26],
  [31, 56],
  [85, 19],
  [11, 69],
  [10, 90],
  [52, 44],
  [9, 2],
  [9, 55],
  [71, 58],
  [18, 21],
  [7, 69],
  [11, 73],
  [76, 5],
  [90, 99],
  [96, 99],
  [39, 83],
  [86, 80],
  [57, 57],
  [19, 6],
  [54, 40],
  [15, 89],
  [10, 3],
  [82, 90],
  [99, 52],
  [65, 90],
  [29, 46],
  [91, 90],
  [95, 41],
  [48, 9],
  [20, 47],
  [43, 33],
  [23, 73],
  [66, 70],
  [65, 49],
  [26, 29],
  [14, 13],
  [15, 77],
  [21, 79],
  [87, 54],
  [83, 72],
  [86, 51],
  [86, 67],
  [66, 90],
  [7, 93],
  [24, 82],
  [29, 14],
  [0, 41],
  [42, 75],
  [89, 24],
  [34, 95],
  [90, 37],
  [8, 13],
  [69, 14],
  [99, 46],
  [22, 50],
  [38, 0],
  [65, 96],
  [70, 10],
  [38, 58],
  [31, 3],
  [20, 45],
  [0, 50],
  [91, 6],
  [54, 78],
  [66, 1],
  [57, 49],
  [81, 16],
  [49, 24],
  [21, 15],
  [51, 66],
  [25, 13],
  [72, 83],
  [43, 47],
  [28, 8],
  [12, 44],
  [89, 56],
  [26, 47],
  [98, 99],
  [48, 93],
  [26, 82],
  [68, 8],
  [60, 30],
  [41, 7],
  [24, 89],
  [65, 64],
  [18, 84],
  [15, 68],
  [44, 7],
  [88, 19],
  [0, 76],
  [69, 53],
  [45, 62],
  [15, 4],
  [49, 27],
  [20, 85],
  [77, 42],
  [34, 23],
  [24, 42],
  [60, 99],
  [41, 25],
  [67, 23],
  [61, 27],
  [91, 15],
  [28, 16],
  [88, 1],
  [46, 94],
  [9, 2],
  [57, 34],
  [59, 93],
  [42, 32],
  [76, 91],
  [24, 35],
  [15, 30],
  [66, 95],
  [60, 13],
  [79, 14],
  [1, 90],
  [20, 24],
  [2, 3],
  [62, 52],
  [16, 76],
  [15, 25],
  [5, 25],
  [61, 41],
  [29, 92],
  [28, 58],
  [0, 5],
  [29, 47],
  [54, 86],
  [4, 87],
  [16, 27],
  [32, 44],
  [68, 90],
  [85, 65],
  [96, 94],
  [86, 64],
  [15, 42],
  [22, 49],
  [77, 1],
  [34, 21],
  [52, 8],
  [79, 41],
  [50, 59],
  [36, 79],
  [76, 39],
  [63, 35],
  [81, 96],
  [10, 68],
  [45, 6],
  [52, 78],
  [36, 7],
  [66, 88],
  [32, 81],
  [7, 70],
  [87, 62],
  [96, 56],
  [16, 15],
  [17, 78],
  [96, 63],
  [71, 35],
  [37, 54],
  [61, 48],
  [95, 14],
  [84, 9],
  [70, 2],
  [73, 80],
  [36, 3],
  [71, 18],
  [50, 31],
  [33, 66],
  [24, 49],
  [93, 38],
  [16, 89],
  [63, 37],
  [39, 41],
  [16, 64],
  [55, 47],
  [13, 44],
  [7, 9],
  [53, 27],
  [40, 18],
  [27, 84],
  [12, 80],
  [4, 39],
  [23, 30],
  [15, 68],
  [98, 72],
  [43, 87],
  [34, 69],
  [21, 73],
  [23, 57],
  [69, 30],
  [59, 32],
  [70, 71],
  [76, 84],
  [37, 63],
  [47, 54],
  [85, 46],
  [87, 93],
  [68, 83],
  [56, 42],
  [27, 7],
  [9, 45],
  [46, 49],
  [96, 43],
  [95, 13],
  [83, 81],
  [51, 9],
  [72, 83],
  [47, 18],
  [68, 71],
  [64, 83],
  [46, 46],
  [62, 21],
  [47, 12],
  [44, 10],
  [6, 73],
  [65, 38],
  [98, 72],
  [39, 77],
  [95, 0],
  [24, 71],
  [49, 6],
  [83, 29],
  [85, 19],
  [98, 21],
  [67, 17],
  [14, 86],
  [21, 33],
  [86, 46],
  [6, 94],
  [6, 51],
  [47, 8],
  [50, 89],
  [21, 64],
  [25, 70],
  [73, 70],
  [90, 83],
  [81, 68],
  [47, 89],
  [87, 57],
  [27, 53],
  [11, 79],
  [43, 42],
  [27, 86],
  [70, 5],
  [97, 34],
  [72, 1],
  [75, 38],
  [54, 7],
  [57, 10],
  [1, 22],
  [4, 28],
  [79, 43],
  [20, 82],
  [94, 71],
  [46, 69],
  [33, 13],
  [37, 2],
  [66, 44],
  [97, 31],
  [97, 31],
  [11, 59],
  [97, 70],
  [53, 20],
  [8, 8],
  [39, 57],
  [60, 14],
  [90, 49],
  [19, 33],
  [19, 89],
  [41, 70],
  [12, 98],
  [42, 75],
  [52, 71],
  [18, 63],
  [80, 56],
  [93, 76],
  [32, 32],
  [93, 66],
  [87, 39],
  [41, 18],
  [78, 73],
  [69, 40],
  [89, 40],
  [82, 56],
  [58, 88],
  [15, 94],
  [39, 95],
  [24, 35],
  [27, 33],
  [91, 8],
  [61, 99],
  [91, 98],
  [58, 26],
  [3, 47],
  [72, 95],
  [58, 52],
  [20, 66],
  [42, 86],
  [88, 69],
  [40, 14],
  [40, 35],
  [38, 45],
  [2, 28],
  [3, 2],
  [77, 59],
  [43, 70],
  [45, 46],
  [78, 2],
  [16, 39],
  [70, 76],
  [33, 52],
  [66, 28],
  [12, 56],
  [93, 29],
  [53, 69],
  [75, 71],
  [58, 37],
  [47, 70],
  [18, 67],
  [20, 66],
  [78, 4],
  [77, 41],
  [51, 89],
  [54, 48],
  [40, 28],
  [72, 82],
  [99, 17],
  [25, 95],
  [58, 13],
  [40, 73],
  [27, 66],
  [16, 51],
  [1, 33],
  [63, 1],
  [72, 76],
  [14, 99],
  [53, 8],
  [62, 42],
  [73, 32],
  [76, 7],
  [88, 54],
  [0, 31],
  [88, 52],
  [6, 64],
  [97, 3],
  [73, 89],
  [3, 66],
  [52, 16],
  [70, 64],
  [49, 10],
  [92, 2],
  [73, 82],
  [41, 62],
  [67, 5],
  [76, 58],
  [32, 16],
  [37, 64],
  [63, 44],
  [33, 63],
  [58, 26],
  [50, 21],
  [92, 65],
  [67, 61],
  [63, 7],
  [0, 54],
  [91, 97],
  [78, 35],
  [80, 53],
  [11, 93],
  [55, 92],
  [30, 2],
  [50, 14],
  [53, 25],
  [8, 54],
  [19, 43],
  [39, 82],
  [13, 19],
  [28, 92],
  [67, 75],
  [51, 30],
  [3, 28],
  [98, 94],
  [1, 73],
  [94, 51],
  [18, 43],
  [67, 92],
  [90, 87],
  [78, 88],
  [97, 50],
  [55, 45],
  [54, 90],
  [49, 13],
  [53, 90],
  [83, 85],
  [63, 81],
  [26, 4],
  [62, 44]],
[[29, 31],
  [54, 86],
  [19, 25],
  [15, 73],
  [75, 56],
  [7, 43],
  [1, 94],
  [41, 10],
  [92, 42],
  [1, 13],
  [42, 76],
  [55, 47],
  [6, 50],
  [29, 63],
  [22, 94],
  [76, 39],
  [29, 64],
  [61, 56],
  [63, 32],
  [39, 26],
  [41, 23],
  [23, 17],
  [41, 63],
  [89, 74],
  [17, 61],
  [54, 41],
  [81, 37],
  [40, 58],
  [20, 29],
  [8, 60],
  [74, 87],
  [22, 29],
  [65, 74],
  [99, 35],
  [20, 80],
  [30, 32],
  [90, 30],
  [37, 53],
  [23, 28],
  [73, 44],
  [61, 96],
  [40, 79],
  [76, 46],
  [33, 30],
  [96, 11],
  [10, 69],
  [83, 96],
  [98, 30],
  [54, 56],
  [23, 26],
  [99, 75],
  [97, 64],
  [90, 66],
  [97, 65],
  [12, 85],
  [83, 41],
  [23, 55],
  [77, 70],
  [68, 34],
  [71, 69],
  [46, 22],
  [11, 75],
  [2, 22],
  [39, 13],
  [15, 32],
  [16, 93],
  [50, 79],
  [41, 88],
  [81, 13],
  [3, 18],
  [33, 62],
  [99, 90],
  [55, 63],
  [13, 36],
  [36, 88],
  [93, 29],
  [39, 96],
  [51, 85],
  [50, 30],
  [39, 34],
  [45, 17],
  [95, 21],
  [28, 15],
  [74, 97],
  [63, 62],
  [57, 9],
  [31, 10],
  [79, 71],
  [69, 93],
  [36, 81],
  [7, 96],
  [14, 20],
  [66, 72],
  [33, 55],
  [18, 61],
  [49, 77],
  [47, 86],
  [74, 91],
  [77, 61],
  [92, 1],
  [59, 26],
  [79, 94],
  [10, 0],
  [26, 40],
  [54, 38],
  [86, 54],
  [92, 96],
  [35, 75],
  [39, 66],
  [50, 19],
  [29, 64],
  [23, 67],
  [83, 68],
  [38, 48],
  [53, 12],
  [22, 69],
  [16, 77],
  [56, 77],
  [99, 33],
  [38, 56],
  [6, 80],
  [8, 35],
  [58, 27],
  [11, 1],
  [66, 10],
  [51, 86],
  [6, 70],
  [83, 72],
  [62, 87],
  [45, 99],
  [46, 1],
  [85, 57],
  [64, 11],
  [64, 95],
  [62, 45],
  [82, 4],
  [28, 68],
  [72, 79],
  [62, 4],
  [61, 37],
  [99, 99],
  [36, 41],
  [61, 39],
  [3, 2],
  [8, 5],
  [4, 31],
  [82, 28],
  [65, 67],
  [11, 26],
  [23, 92],
  [89, 68],
  [73, 88],
  [86, 9],
  [42, 95],
  [8, 57],
  [78, 4],
  [12, 29],
  [27, 16],
  [81, 87],
  [43, 39],
  [63, 24],
  [24, 69],
  [61, 16],
  [97, 99],
  [38, 68],
  [14, 36],
  [50, 35],
  [49, 13],
  [46, 72],
  [35, 8],
  [3, 53],
  [79, 71],
  [68, 84],
  [16, 41],
  [44, 27],
  [65, 30],
  [46, 43],
  [97, 65],
  [35, 96],
  [20, 42],
  [51, 6],
  [30, 56],
  [94, 38],
  [47, 22],
  [47, 14],
  [15, 13],
  [27, 94],
  [94, 23],
  [4, 88],
  [81, 14],
  [69, 9],
  [17, 37],
  [75, 88],
  [35, 37],
  [56, 96],
  [7, 10],
  [63, 89],
  [67, 99],
  [14, 94],
  [81, 93],
  [86, 10],
  [81, 3],
  [9, 35],
  [30, 96],
  [19, 23],
  [42, 6],
  [55, 46],
  [40, 95],
  [54, 4],
  [43, 23],
  [15, 44],
  [29, 83],
  [10, 20],
  [35, 15],
  [51, 71],
  [44, 41],
  [42, 96],
  [54, 10],
  [92, 26],
  [74, 61],
  [86, 46],
  [89, 4],
  [89, 7],
  [7, 49],
  [98, 41],
  [76, 0],
  [81, 78],
  [17, 62],
  [0, 18],
  [64, 21],
  [12, 72],
  [9, 68],
  [16, 11],
  [51, 57],
  [36, 83],
  [28, 28],
  [29, 4],
  [53, 42],
  [75, 92],
  [46, 51],
  [63, 70],
  [37, 68],
  [17, 24],
  [44, 93],
  [27, 33],
  [61, 22],
  [64, 3],
  [50, 5],
  [3, 38],
  [98, 96]],
[[89, 85],
  [69, 65],
  [4, 96],
  [94, 35],
  [69, 88],
  [4, 48],
  [32, 51],
  [43, 50],
  [73, 28],
  [42, 91],
  [50, 80],
  [22, 74],
  [50, 53],
  [70, 68],
  [78, 99],
  [72, 38],
  [18, 90],
  [8, 45],
  [91, 26],
  [97, 44],
  [44, 67],
  [59, 0],
  [60, 31],
  [40, 34],
  [40, 40],
  [58, 57],
  [58, 49],
  [44, 4],
  [31, 87],
  [27, 19],
  [92, 30],
  [56, 90],
  [72, 92],
  [15, 48],
  [46, 19],
  [28, 8],
  [1, 34],
  [45, 57],
  [84, 77],
  [57, 63],
  [12, 81],
  [7, 85],
  [14, 22],
  [57, 89],
  [70, 19],
  [73, 59],
  [29, 42],
  [32, 58],
  [26, 47],
  [63, 90],
  [93, 68],
  [14, 96],
  [82, 37],
  [31, 13],
  [37, 15],
  [22, 5],
  [47, 15],
  [79, 34],
  [37, 22],
  [43, 65],
  [52, 70],
  [28, 53],
  [66, 69],
  [14, 76],
  [43, 64],
  [47, 77],
  [18, 29],
  [76, 61],
  [75, 13],
  [61, 79],
  [31, 90],
  [37, 87],
  [82, 44],
  [34, 5],
  [60, 93],
  [28, 75],
  [43, 44],
  [98, 97],
  [19, 57],
  [89, 89],
  [80, 93],
  [0, 60],
  [11, 93],
  [95, 77],
  [81, 6],
  [17, 60],
  [71, 99],
  [11, 12],
  [5, 49],
  [52, 21],
  [70, 34],
  [71, 58],
  [13, 86],
  [41, 84],
  [90, 5],
  [31, 2],
  [99, 74],
  [2, 78],
  [50, 8],
  [12, 78],
  [42, 6],
  [38, 17],
  [56, 41],
  [84, 96],
  [37, 63],
  [22, 96],
  [8, 84],
  [48, 12],
  [49, 72],
  [10, 36],
  [15, 25],
  [87, 34],
  [12, 4],
  [2, 43],
  [8, 51],
  [63, 1],
  [53, 47],
  [41, 25],
  [87, 24],
  [41, 65],
  [53, 95],
  [27, 83],
  [27, 72],
  [20, 31],
  [59, 70],
  [42, 41],
  [73, 27],
  [12, 45],
  [30, 97],
  [59, 1],
  [22, 76],
  [92, 81],
  [46, 88],
  [36, 88],
  [93, 44],
  [92, 44],
  [84, 98],
  [66, 95],
  [61, 25],
  [41, 75],
  [58, 90],
  [51, 26],
  [72, 82],
  [25, 0],
  [23, 43],
  [60, 46],
  [74, 46],
  [2, 5],
  [38, 21],
  [69, 75],
  [8, 79],
  [74, 75],
  [37, 62],
  [44, 38],
  [61, 64],
  [53, 58],
  [33, 86],
  [69, 49],
  [62, 79],
  [58, 34],
  [80, 39],
  [25, 32],
  [49, 8],
  [21, 93],
  [54, 97],
  [17, 73],
  [26, 43],
  [1, 21],
  [15, 26],
  [31, 33],
  [36, 75],
  [50, 14],
  [28, 41],
  [2, 36],
  [42, 8],
  [57, 89],
  [66, 1],
  [68, 21],
  [24, 16],
  [19, 31],
  [48, 91],
  [40, 28],
  [1, 11],
  [83, 51],
  [48, 94],
  [80, 71],
  [17, 39],
  [55, 76],
  [99, 2],
  [83, 39],
  [35, 34],
  [43, 23],
  [93, 76],
  [50, 81],
  [72, 14],
  [77, 71],
  [13, 35],
  [32, 31],
  [98, 80],
  [0, 71],
  [69, 92],
  [80, 91],
  [79, 70],
  [44, 39],
  [54, 6],
  [82, 67],
  [45, 44],
  [67, 1],
  [16, 21],
  [98, 10],
  [71, 35],
  [13, 91],
  [24, 7],
  [42, 24],
  [11, 93],
  [29, 83],
  [75, 57],
  [42, 91],
  [43, 31],
  [84, 10],
  [26, 35],
  [79, 34],
  [33, 82],
  [36, 16],
  [21, 97],
  [18, 57],
  [24, 4],
  [45, 71],
  [53, 55],
  [80, 90],
  [15, 87],
  [97, 42],
  [66, 74],
  [66, 13],
  [97, 66],
  [8, 75],
  [34, 99],
  [78, 62],
  [35, 93],
  [54, 98],
  [14, 25],
  [82, 30],
  [65, 77],
  [6, 7],
  [25, 86],
  [66, 99],
  [95, 91],
  [23, 8],
  [33, 27],
  [86, 15],
  [75, 42],
  [61, 65],
  [32, 81],
  [92, 6],
  [79, 61],
  [50, 84],
  [60, 51],
  [55, 19],
  [79, 24],
  [95, 89],
  [24, 20],
  [55, 52],
  [43, 46],
  [99, 21],
  [34, 7],
  [55, 55],
  [69, 21],
  [46, 52],
  [19, 74],
  [38, 57],
  [91, 39],
  [65, 11],
  [90, 42],
  [19, 34],
  [15, 10],
  [88, 40],
  [89, 32],
  [95, 94],
  [25, 93],
  [27, 37],
  [86, 81],
  [25, 37],
  [5, 22],
  [37, 65],
  [34, 58],
  [25, 77],
  [20, 73],
  [98, 72],
  [31, 61],
  [18, 31],
  [5, 80],
  [40, 77],
  [39, 97],
  [35, 95],
  [23, 92],
  [25, 84],
  [42, 58],
  [48, 49],
  [18, 68],
  [11, 65],
  [56, 99],
  [25, 42],
  [8, 61],
  [53, 67],
  [18, 10],
  [72, 82],
  [4, 32],
  [67, 85],
  [69, 40],
  [66, 65],
  [21, 14],
  [22, 61],
  [85, 1],
  [83, 54],
  [29, 96],
  [42, 29],
  [18, 97],
  [58, 83],
  [25, 84],
  [66, 7],
  [93, 84],
  [62, 39],
  [6, 86],
  [74, 96],
  [37, 36],
  [89, 40],
  [68, 16],
  [41, 80],
  [26, 46],
  [85, 90],
  [14, 95],
  [86, 90],
  [75, 89],
  [48, 40],
  [37, 45],
  [18, 35],
  [14, 13],
  [43, 47],
  [26, 78],
  [21, 25],
  [8, 65],
  [43, 62],
  [49, 55],
  [64, 68],
  [85, 79],
  [22, 23],
  [95, 80],
  [36, 98],
  [10, 4],
  [19, 67],
  [54, 99],
  [89, 43],
  [94, 53],
  [96, 27],
  [89, 4],
  [56, 71],
  [14, 61],
  [83, 54],
  [24, 17],
  [21, 93],
  [50, 70],
  [97, 46],
  [5, 77],
  [97, 86],
  [98, 99],
  [41, 37],
  [63, 70],
  [14, 74],
  [1, 80],
  [69, 16],
  [53, 13],
  [31, 84],
  [73, 21],
  [38, 97],
  [22, 35],
  [58, 89],
  [1, 63],
  [24, 7],
  [97, 94],
  [30, 2],
  [58, 98],
  [35, 10],
  [93, 35],
  [60, 29],
  [74, 94],
  [31, 97],
  [41, 30],
  [50, 25],
  [47, 17],
  [17, 57],
  [93, 19],
  [74, 56],
  [19, 65],
  [40, 89],
  [42, 89],
  [52, 5],
  [75, 26],
  [23, 18],
  [75, 13],
  [25, 64],
  [35, 95],
  [85, 18],
  [57, 85],
  [65, 53],
  [86, 25],
  [7, 14],
  [28, 19],
  [71, 16],
  [78, 32],
  [48, 42],
  [51, 30],
  [58, 62],
  [25, 30],
  [36, 11],
  [72, 79],
  [43, 31],
  [17, 37],
  [53, 18],
  [24, 74],
  [2, 78],
  [0, 80],
  [87, 24],
  [42, 25],
  [15, 94],
  [69, 65],
  [88, 70],
  [30, 41],
  [20, 93],
  [54, 0],
  [74, 4],
  [65, 45],
  [54, 76],
  [49, 38],
  [68, 58],
  [11, 90],
  [97, 76],
  [65, 63],
  [4, 52],
  [96, 95],
  [51, 46],
  [13, 63],
  [2, 82],
  [16, 13],
  [94, 7],
  [80, 77],
  [33, 14],
  [1, 47],
  [49, 62],
  [31, 86],
  [39, 24],
  [76, 22],
  [44, 13],
  [55, 23],
  [2, 68],
  [59, 98],
  [56, 54],
  [61, 34],
  [2, 99],
  [30, 23],
  [39, 50],
  [52, 60],
  [85, 50],
  [96, 97],
  [4, 74],
  [54, 71],
  [83, 35],
  [1, 17],
  [83, 96],
  [95, 14],
  [22, 83],
  [44, 22],
  [48, 70],
  [24, 20],
  [73, 73],
  [61, 79],
  [4, 82],
  [20, 58],
  [20, 80],
  [1, 87],
  [97, 22],
  [52, 48],
  [10, 1],
  [6, 65],
  [42, 31],
  [30, 49],
  [71, 51],
  [47, 56],
  [31, 24],
  [57, 23],
  [43, 97],
  [30, 12],
  [76, 47],
  [97, 71],
  [92, 38],
  [49, 78],
  [79, 88],
  [87, 31],
  [28, 24],
  [99, 29],
  [65, 69]],
[[56, 46],
  [94, 2],
  [33, 0],
  [50, 15],
  [5, 61],
  [12, 88],
  [28, 68],
  [44, 69],
  [4, 22],
  [64, 33],
  [99, 57],
  [89, 75],
  [38, 91],
  [29, 42],
  [60, 71],
  [5, 8],
  [22, 89],
  [82, 69],
  [42, 28],
  [27, 23],
  [42, 28],
  [81, 57],
  [88, 35],
  [10, 94],
  [20, 58],
  [3, 80],
  [30, 80],
  [71, 89],
  [50, 78],
  [73, 3],
  [6, 42],
  [45, 65],
  [65, 63],
  [94, 58],
  [29, 71],
  [94, 30],
  [64, 63],
  [10, 13],
  [63, 18],
  [48, 45],
  [88, 66],
  [99, 55],
  [99, 86],
  [21, 57],
  [25, 7],
  [51, 66],
  [18, 63],
  [5, 20],
  [67, 60],
  [50, 57],
  [34, 6],
  [76, 2],
  [66, 11],
  [12, 12],
  [13, 15],
  [48, 62],
  [97, 95],
  [1, 76],
  [7, 1],
  [10, 22],
  [65, 7],
  [71, 46],
  [68, 17],
  [46, 40],
  [39, 92],
  [34, 81],
  [4, 95],
  [61, 88],
  [49, 77],
  [72, 69],
  [78, 56],
  [73, 18],
  [93, 67],
  [97, 86],
  [98, 29],
  [16, 32],
  [28, 39],
  [40, 52],
  [6, 40],
  [22, 74],
  [75, 53],
  [76, 99],
  [89, 4],
  [39, 31],
  [66, 36],
  [13, 90],
  [21, 73],
  [83, 16],
  [76, 29],
  [88, 22],
  [60, 9],
  [74, 42],
  [9, 95],
  [9, 39],
  [77, 27],
  [15, 94],
  [79, 69],
  [80, 56],
  [84, 60],
  [3, 28],
  [10, 16],
  [53, 73],
  [66, 1],
  [15, 63],
  [62, 21],
  [35, 33],
  [21, 65],
  [97, 3],
  [84, 37],
  [40, 92],
  [20, 38],
  [94, 12],
  [87, 99],
  [4, 28],
  [26, 53],
  [99, 78],
  [22, 56],
  [19, 51],
  [51, 5],
  [38, 22],
  [18, 5],
  [57, 57],
  [10, 31],
  [89, 40],
  [41, 4],
  [57, 10],
  [10, 23],
  [19, 68],
  [47, 55],
  [91, 75],
  [71, 71],
  [95, 50],
  [36, 0],
  [16, 96],
  [49, 47],
  [62, 38],
  [2, 12],
  [51, 92],
  [9, 4],
  [83, 30],
  [65, 68],
  [60, 63],
  [10, 46],
  [76, 30],
  [40, 54],
  [15, 83],
  [79, 12],
  [21, 98],
  [22, 73],
  [31, 67],
  [97, 90],
  [74, 9],
  [1, 9],
  [95, 60],
  [39, 85],
  [41, 73],
  [84, 62],
  [76, 12],
  [41, 62],
  [89, 98],
  [44, 44],
  [44, 54],
  [25, 25],
  [3, 23],
  [36, 49],
  [77, 93],
  [67, 54],
  [71, 86],
  [26, 76],
  [73, 32],
  [76, 51],
  [55, 75],
  [49, 5],
  [96, 33],
  [45, 47],
  [49, 29],
  [37, 3],
  [76, 84],
  [20, 19],
  [82, 99],
  [37, 41],
  [46, 55],
  [62, 11],
  [44, 65],
  [52, 36],
  [45, 54],
  [66, 4],
  [14, 27],
  [17, 69],
  [46, 49],
  [87, 23],
  [64, 12],
  [76, 63],
  [74, 27],
  [25, 64],
  [80, 64],
  [74, 28],
  [17, 36],
  [79, 4],
  [20, 82],
  [88, 69],
  [9, 46],
  [7, 13],
  [39, 54],
  [84, 23],
  [96, 56],
  [13, 26],
  [85, 21],
  [45, 28],
  [53, 23],
  [97, 68],
  [85, 92],
  [17, 11],
  [18, 84],
  [91, 15],
  [25, 99],
  [65, 93],
  [17, 67],
  [68, 55],
  [2, 15],
  [18, 72],
  [33, 96],
  [40, 98],
  [55, 29],
  [18, 30],
  [29, 24],
  [50, 0],
  [22, 42],
  [90, 34],
  [35, 79],
  [32, 57],
  [14, 44],
  [27, 23],
  [52, 98],
  [57, 95],
  [19, 79],
  [52, 43],
  [76, 90],
  [92, 67],
  [86, 9],
  [62, 79],
  [63, 92],
  [22, 2],
  [74, 45],
  [53, 37],
  [72, 89],
  [73, 14],
  [91, 74],
  [84, 58],
  [67, 53]],
[[16, 56],
  [37, 97],
  [46, 84],
  [55, 17],
  [11, 63],
  [55, 16],
  [81, 24],
  [47, 52],
  [88, 26],
  [72, 95],
  [77, 85],
  [57, 0],
  [72, 92],
  [24, 61],
  [5, 38],
  [79, 99],
  [86, 70],
  [46, 65],
  [21, 46],
  [83, 68],
  [17, 59],
  [73, 11],
  [55, 71],
  [96, 75],
  [49, 83],
  [48, 97],
  [19, 43],
  [51, 62],
  [16, 48],
  [77, 92],
  [23, 86],
  [74, 48],
  [63, 51],
  [46, 0],
  [86, 1],
  [2, 95],
  [5, 54],
  [5, 2],
  [87, 59],
  [9, 69],
  [1, 7],
  [99, 35],
  [4, 54],
  [47, 46],
  [54, 20],
  [42, 43],
  [57, 74],
  [82, 34],
  [4, 84],
  [50, 65],
  [66, 68],
  [98, 3],
  [75, 68],
  [10, 31],
  [49, 52],
  [59, 96],
  [37, 19],
  [71, 34],
  [66, 18],
  [99, 45],
  [20, 1],
  [23, 22],
  [76, 99],
  [92, 12],
  [35, 46],
  [42, 66],
  [66, 84],
  [77, 76],
  [3, 10],
  [74, 3],
  [70, 75],
  [51, 79],
  [64, 67],
  [1, 89],
  [46, 84],
  [42, 6],
  [52, 42],
  [46, 59],
  [91, 21],
  [13, 62],
  [81, 55],
  [77, 93],
  [27, 11],
  [83, 75],
  [81, 98],
  [94, 7],
  [73, 59],
  [82, 67],
  [76, 24],
  [48, 47],
  [85, 96],
  [42, 6],
  [78, 42],
  [48, 7],
  [95, 69],
  [26, 73],
  [83, 16],
  [76, 98],
  [40, 94],
  [97, 18],
  [54, 87],
  [77, 30],
  [69, 67],
  [34, 7],
  [10, 24],
  [64, 32],
  [33, 89],
  [36, 33],
  [48, 35],
  [88, 84],
  [93, 77],
  [23, 57],
  [35, 38],
  [55, 29],
  [49, 57],
  [78, 31],
  [96, 12],
  [30, 88],
  [5, 41],
  [10, 87],
  [91, 9],
  [64, 60],
  [74, 33],
  [10, 3],
  [37, 78],
  [83, 39],
  [51, 15],
  [21, 0],
  [13, 48],
  [2, 74],
  [44, 43],
  [88, 23],
  [1, 60],
  [90, 74],
  [79, 74],
  [82, 45],
  [8, 83],
  [49, 20],
  [53, 7],
  [1, 33],
  [19, 4],
  [19, 45],
  [35, 43],
  [64, 54],
  [98, 25],
  [5, 56],
  [43, 75],
  [54, 90],
  [3, 13],
  [59, 61],
  [21, 40],
  [46, 29],
  [37, 31],
  [38, 46],
  [19, 43],
  [30, 34],
  [76, 68],
  [2, 41],
  [69, 0],
  [96, 33],
  [25, 20],
  [42, 34],
  [98, 14],
  [30, 23],
  [9, 98],
  [10, 92],
  [1, 10],
  [92, 47],
  [53, 26],
  [52, 2],
  [53, 84],
  [87, 44],
  [10, 6],
  [57, 17],
  [82, 26],
  [15, 72],
  [20, 54],
  [34, 95],
  [61, 5],
  [34, 96],
  [14, 68],
  [9, 50],
  [48, 46],
  [34, 0],
  [88, 52],
  [15, 20],
  [52, 3],
  [23, 18],
  [84, 94],
  [6, 9],
  [84, 75],
  [31, 10],
  [16, 21],
  [15, 13],
  [22, 99],
  [62, 76],
  [13, 82],
  [99, 82],
  [53, 82],
  [29, 87],
  [53, 47],
  [98, 59],
  [48, 93],
  [72, 50],
  [18, 93],
  [93, 91],
  [12, 99],
  [2, 79],
  [0, 35],
  [45, 66],
  [75, 69],
  [10, 72],
  [33, 27],
  [42, 10],
  [76, 72],
  [93, 12],
  [68, 6],
  [92, 9],
  [15, 61],
  [90, 96],
  [73, 17],
  [8, 50],
  [19, 0],
  [55, 52],
  [97, 21],
  [25, 62],
  [13, 34],
  [75, 62],
  [14, 65],
  [35, 21],
  [44, 70],
  [2, 6],
  [69, 65],
  [48, 95],
  [97, 44],
  [29, 73],
  [57, 62],
  [49, 7],
  [6, 6],
  [98, 9],
  [77, 29],
  [87, 16],
  [10, 94],
  [7, 18],
  [89, 95],
  [81, 55],
  [30, 60],
  [3, 77],
  [45, 68],
  [67, 47]]
]

In [9]:
[components(100, graf) for graf in grafi]


Out[9]:
[1, 2, 2, 3, 3, 4]