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]:
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]: