Queries to check if vertices X and Y are in the same Connected Component of an Undirected Graph | Maximum number of nodes or vertices that can be present in the graph ; Store the parent of each vertex ; Stores the size of each set ; Function to initialize the parent of each vertices ; Function to find the representative of the set which contain element v ; Path compression technique to optimize the time complexity ; Function to merge two different set into a single set by finding the representative of each set and merge the smallest set with the larger one ; Finding the set representative of each element ; Check if they have different set repersentative ; Compare the set sizes ; Assign parent of smaller set to the larger one ; Add the size of smaller set to the larger one ; Function to check the vertices are on the same set or not ; Check if they have same set representative or not ; Driver code ; Connected vertices and taking them into single set ; Number of queries ; Function call
MAX_NODES = 100005 NEW_LINE parent = [ 0 for i in range ( MAX_NODES ) ] ; NEW_LINE size_set = [ 0 for i in range ( MAX_NODES ) ] ; NEW_LINE def make_set ( v ) : NEW_LINE INDENT parent [ v ] = v ; NEW_LINE size_set [ v ] = 1 ; NEW_LINE DEDENT def find_set ( v ) : NEW_LINE INDENT if ( v == parent [ v ] ) : NEW_LINE INDENT return v ; NEW_LINE DEDENT parent [ v ] = find_set ( parent [ v ] ) ; NEW_LINE return parent [ v ] NEW_LINE DEDENT def union_set ( a , b ) : NEW_LINE INDENT a = find_set ( a ) ; NEW_LINE b = find_set ( b ) ; NEW_LINE if ( a != b ) : NEW_LINE INDENT if ( size_set [ a ] < size_set [ b ] ) : NEW_LINE INDENT swap ( a , b ) ; NEW_LINE DEDENT parent [ b ] = a ; NEW_LINE size_set [ a ] += size_set [ b ] ; NEW_LINE DEDENT DEDENT def check ( a , b ) : NEW_LINE INDENT a = find_set ( a ) ; NEW_LINE b = find_set ( b ) ; NEW_LINE if a == b : NEW_LINE INDENT return ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT return ( " No " ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 5 NEW_LINE m = 3 ; NEW_LINE make_set ( 1 ) ; NEW_LINE make_set ( 2 ) ; NEW_LINE make_set ( 3 ) ; NEW_LINE make_set ( 4 ) ; NEW_LINE make_set ( 5 ) ; NEW_LINE union_set ( 1 , 3 ) ; NEW_LINE union_set ( 3 , 4 ) ; NEW_LINE union_set ( 3 , 5 ) ; NEW_LINE q = 3 ; NEW_LINE print ( check ( 1 , 5 ) ) NEW_LINE print ( check ( 3 , 2 ) ) NEW_LINE print ( check ( 5 , 2 ) ) NEW_LINE DEDENT