class Trie {
class TrieNode{
Map<Character,TrieNode> children = new HashMap<>();
boolean isLeaf;
}
private TrieNode root;
/** Initialize your data structure here. */
public Trie() {
root= new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode node = root;
for(char c : word.toCharArray()){
if(!node.children.containsKey(c)){
node.children.put(c,new TrieNode());
}
node = node.children.get(c);
}
node.isLeaf= true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode p = root;
for(char c : word.toCharArray()) {
if(!p.children.containsKey(c)) {
return false;
}
p = p.children.get(c);
}
return p.isLeaf;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode p = root;
for(char c : prefix.toCharArray()) {
if(!p.children.containsKey(c)) {
return false;
}
p = p.children.get(c);
}
return true;
}
}class DSU{
//path compression and union by rank
int[] parent;
int[] rank;
int components;
public DSU(int components){
this.components=components;
parent = new int[components];
for(int i =0 ; i<components;i++){
parent[i]=i;//initially node is the parent of itself
}
rank = new int[components]; //initial rank=0
}
public int find(int node){
if(parent[node]!=node) {
parent[node]=find(parent[node]);
}
return parent[node];
}
public boolean union(int x, int y){
int px = find(x);
int py = find(y);
if(px==py) return false;
else{
else if (rank[px]<rank[py]) parent[px]=py;
else if(rank[px]>rank[py]) parent[py]=px;
else {
parent[py]=px;
rank[px]++;
}
componenets--;
}
return true;
}
}
