Lernen mit disjunkten Mengengraphen

class Main{ int parent[] = new int[100000]; int rank[] = new int[100000]; void makeSet(){ for(int i=1;i<=n;i++){ parent[i] = i; // initially parent of node i is i itself rank[i] =0;// intially rank of all the nodes are 0 } } int findParent(int node){ if(node == parent[node]) return node; // ie if the parent of 'node' is 'node' itself then just return the node. //return findParent(parent[node]);// else recursively call findParent to get the parent of this union. // in order to path conpress (making sure that every node is connected to its parent in the given union) return parent[node] = findParent(parent[node]); //example : 7->6->4->3 , here 3 is the parent of this union, so in order to get the parent of 7 which is 3 we can path compress it. like 7->3,6->3,4->3 etc. } void union(int u, int v){ u = findParent(u); v = findParent(v); if(rank[u] < rank[v]) parent[u] =v; else if (rank[u] > rank[v]) parent[v] = u; else parent[u] =v; // or parent[v] = u; // here u and v had the same rank //and now v became parent of u hence its rank will increase rank[v]++; } public static void main(String args[]) throws Exception{ Main m = new Main(); //if we where given no of nodes as n BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); while(n>0){ int u = n--; int v = n--; m.union(u,v);// this will create union of n nodes } // if 2 and 3 belong to the same component or not find out if(findParent(2)! = findParent(3)) System.out.println("Different component"); else System.out.println("Same component"); } }