efficiently find connected components in undirected graph considering transitive equivalence I have a set of nodes and a function foo(u,v) that can determine whether two nodes are equal. By "equal" I mean transitive equivalence:
 If 1==2 and 2==3 then 1==3 and also: If 1==2 and 1!=4 then 2!=4

When given a set of nodes I can find all connected components in the graph by passing every possible combination of nodes to foo(u,v) function and building the needed edges. Like this:

import networkx as nx
import itertools
from matplotlib import pyplot as plt

EQUAL_EDGES = {(1, 2), (1, 3), (4, 5)}


def foo(u, v):
    # this function is simplified, in reality it will do a complex calculation to determine whether nodes are equal.
    return (u, v) in EQUAL_EDGES


def main():
    g = nx.Graph()
    g.add_nodes_from(range(1, 5 + 1))
    for u, v in itertools.combinations(g.nodes, 2):
        are_equal = foo(u, v)
        print '{u}{sign}{v}'.format(u=u, v=v, sign='==' if are_equal else '!=')
        if are_equal:
            g.add_edge(u, v)

    conn_comps = nx.connected_components(g)
    nx.draw(g, with_labels=True)
    plt.show()
    return conn_comps


if __name__ == '__main__':
    main()


the problem with this approach  is that I get many redundant checks that I would like to avoid:

1==2  # ok
1==3  # ok
1!=4  # ok
1!=5  # ok
2!=3  # redundant check, if 1==2 and 1==3 then 2==3 
2!=4  # redundant check, if 1!=4 and 1==2 then 2!=4 
2!=5  # redundant check, if 1!=5 and 1==2 then 2!=5
3!=4  # redundant check, if 1!=4 and 1==3 then 3!=4
3!=5  # redundant check, if 1!=5 and 1==3 then 3!=5
4==5  # ok


I want to avoid running in O(n^2) time complexity.
What is the correct way (or maybe an existing function in any python library) to efficiently find all connected components by a custom function?
Using depth-first search, compute the connected components, by constructing a mapping that maps each node in a connected component to the first node you visited in that component. This is linear in the number of nodes and edges. Preserve that mapping. Two nodes are equivalent if and only if they map to the same node.