Union | Java program to implement Union - Find with union by rank and path compression ; Arr to represent parent of index i ; Size to represent the number of nodes in subgxrph rooted at index i ; set parent of every node to itself and size of node to one ; Each time we follow a path , find function compresses it further until the path length is greater than or equal to 1. ; while we reach a node whose parent is equal to itself ; Skip one level ; Move to the new level ; A function that does union of two nodes x and y where xr is root node of x and yr is root node of y ; Make yr parent of xr ; Make xr parent of yr ; The main function to check whether a given gxrph contains cycle or not ; Itexrte through all edges of gxrph , find nodes connecting them . If root nodes of both are same , then there is cycle in gxrph . ; find root of i ; find root of adj [ i ] [ j ] ; If same parent ; Make them connect ; Driver Code ; Initialize the values for arxry Arr and Size ; Adjacency list for graph ; call is_cycle to check if it contains cycle
import java . util . * ; class GFG { static int MAX_VERTEX = 101 ; static int [ ] Arr = new int [ MAX_VERTEX ] ; static int [ ] size = new int [ MAX_VERTEX ] ; static void initialize ( int n ) { for ( int i = 0 ; i <= n ; i ++ ) { Arr [ i ] = i ; size [ i ] = 1 ; } } static int find ( int i ) { while ( Arr [ i ] != i ) { Arr [ i ] = Arr [ Arr [ i ] ] ; i = Arr [ i ] ; } return i ; } static void _union ( int xr , int yr ) { if ( size [ xr ] < size [ yr ] ) { Arr [ xr ] = Arr [ yr ] ; size [ yr ] += size [ xr ] ; } else { Arr [ yr ] = Arr [ xr ] ; size [ xr ] += size [ yr ] ; } } static int isCycle ( Vector < Integer > adj [ ] , int V ) { for ( int i = 0 ; i < V ; i ++ ) { for ( int j = 0 ; j < adj [ i ] . size ( ) ; j ++ ) { int x = find ( i ) ; int y = find ( adj [ i ] . get ( j ) ) ; if ( x == y ) return 1 ; _union ( x , y ) ; } } return 0 ; } public static void main ( String [ ] args ) { int V = 3 ; initialize ( V ) ; Vector < Integer > [ ] adj = new Vector [ V ] ; for ( int i = 0 ; i < V ; i ++ ) adj [ i ] = new Vector < Integer > ( ) ; adj [ 0 ] . add ( 1 ) ; adj [ 0 ] . add ( 2 ) ; adj [ 1 ] . add ( 2 ) ; if ( isCycle ( adj , V ) == 1 ) System . out . print ( "Graph contains Cycle.NEW_LINE"); else System . out . print ( "Graph does not contain Cycle.NEW_LINE"); } }